Patent ID: 8156412

Claim:
A tree decoding method for decoding a linear block code (n, k), the linear block code having a generator matrix G, where c=(c 0 , c 1 , . . . , c n−1 ) represents a transmitted codeword, r=(r 0 , r 1 , . . . , r n−1 ) represents a received signal, n represents a length of the codeword, and k represents a length of information bits, the tree decoding method comprising the steps of: (1) setting a sequence of the received signal r=(r 0 , r 1 , . . . , r n−1 ) in accordance with reliabilities thereof, respectively, thus obtaining r′, and exchanging columns of the generator matrix G of r, thus obtaining G*, and then simplifying G* to obtain a systematic generator matrix G′ as well as a code tree of G′, where a path of the code tree is a codeword c′=(c′ 0 , c′ 1 , . . . , c ′ n−1 ), wherein c′ comprises k information bits (u 0 , u 1 , . . . , u k−1 ) and n-k parity bits (p k , p k+1, . . . , p n−1 ); (2) according to the code tree of G′, providing a bit metric M b (c′ i , r′ i ) corresponding to c′ i , and r′ i , functions f, g, h, and a stack, wherein with respect to a node having a code number v, i.e., node v, it is assigned that f(v)=g(v)+h(v), wherein g(v) represents a sum of bit metrics of all bits on a path from the root node to the node v, and h(v) is determined in that when there is any parity bit between the node v and a goal node that can be determined by the information bits between the root node and the node v, the bit metric of the parity bit is accumulated to h(v), otherwise h(v)=0; (3) assigning the root node as a pointer node, i.e., node v, which g(v)=0 and h(v)=0, setting a very poor metric value as an initial f(v best ), and setting an initial node of v best as v ∞ , wherein v ∞ is a virtual node; (4) emanating from the pointer node to descendant nodes, and when the f(v) of the descendant node is better than f(v best ), recording the descendant node in the stack; (5) selecting the best node v from the stack and assigning the selected node v as the pointer node, wherein if the path from the root node to the pointer node does not include all information bits, the method returns back to step ( 4 ); (6) till now, the path from the root node to the pointer node comprising all of the information bits, and an estimated path metric of the entire codeword passing through the node v being f(v), and if f(v) is worse than or equal to f(v best ), then discarding node v, otherwise if f(v) is better than f(v best ), then assigning v best =v, and eliminating each node w in the stack for f(w) is worse than f(v); and (7) if v best is the only node left in the stack, conducting a reverse operation of the sequence setting of step 1 to the codeword passing through v best to obtain an original codeword, and if there are more than 1 node left in the stack, then turning back to step ( 5 ).