Tanner Graph
A bipartite graph describing the structure of a linear code. One side consists of variable nodes (corresponding to codeword bits) and the other of check nodes (corresponding to parity-check equations); edges indicate which bits participate in which check equations. It is the underlying graph structure for BP decoding.
Timeline (last 90 days)
The belief propagation (BP) algorithm performs iterative message passing on the Tanner graph and is the mainstream method for linear code decoding, but under certain code types and channel conditions its convergence and decoding accuracy are unsatisfactory.
A Tanner graph is a bipartite graph describing the structure of a linear code, with variable nodes (corresponding to codeword bits) on one side and check nodes (corresponding to check equations) on the other, and an edge connects a bit and a check equation when the bit participates in that check equation.
BP decoding alternates iteratively on the Tanner graph between variable nodes sending posterior information to check nodes and check nodes sending check information back to variable nodes.
The sparsity of the Tanner graph determines the computational complexity of BP, while the presence of short cycles (girth) in the graph undermines the independence assumption of messages and thereby causes convergence difficulties.
All Facts (4)
The belief propagation (BP) algorithm performs iterative message passing on the Tanner graph and is the mainstream method for linear code decoding, but under certain code types and channel conditions its convergence and decoding accuracy are unsatisfactory.
50%UnverifiedA Tanner graph is a bipartite graph describing the structure of a linear code, with variable nodes (corresponding to codeword bits) on one side and check nodes (corresponding to check equations) on the other, and an edge connects a bit and a check equation when the bit participates in that check equation.
50%UnverifiedBP decoding alternates iteratively on the Tanner graph between variable nodes sending posterior information to check nodes and check nodes sending check information back to variable nodes.
50%UnverifiedThe sparsity of the Tanner graph determines the computational complexity of BP, while the presence of short cycles (girth) in the graph undermines the independence assumption of messages and thereby causes convergence difficulties.
50%