Patent ID: 7266749

Claim:
A method of constructing a simplified trellis diagram for BCH encoding of information, the method comprising: receiving information having a corresponding (n−k)×(n) parity check matrix H, constructed according to a BCH error code, where n and k are selected positive integers with k<n; expressing the parity check matrix H as an ordered sequence of columns of matrices {h 1 , h 2 , . . . , h n }; providing a sequence of sub-code words a i ={c 1 , . . . , c i } (i=1, . . . , n), corresponding to at least one code word c={c 1 , . . . , c n } that satisfies c·H tr =0 n−k ; applying a column-permutation-for-binary-matching process to the columns of the matrix H to provide a matrix H cp , having columns {h cp 1 , h cp 2 , . . . , h cp n } that are a selected permutation of the columns of the matrix H; providing a sequence of sub-matrices H cp i ={h cp 1 , . . . , h cp i }, providing a corresponding permuted code word c cp ={c cp 1 , . . . , c cp n }, and providing a sequence of corresponding permuted sub-code words a cp i ={c cp 1 , . . . , c cp i }; and generating a trellis diagram, symmetric about a central location and representing an ordered sequence of code word transitions, in the received information, for the at least one code word c, connecting n+1 stages, numbered i=0, 1, . . . , n, in an ordered sequence, where each of stage i=0 and stage i=n in the trellis has one state, each stage has at least one state, and (i) where the number of states in stage i+1 is no greater than the number of states in stage i, the number of input branches for each state in stage i+1 is 2, (ii) where the number of states in stage i+1 is greater than the number of states in stage i, the number of input branches for each state in stage i+1 is 1, and (iii) a state in stage i+1 is determined by a sum of a corresponding state in stage i and a product of the matrix H cp i and the sub-code word bit value a cp i .