Patent ID: 6536009
Filing Date: 2003-03-18
Classification: G06F

Abstract:
A method of generating a parity check matrix H for a single-bit error-correcting, two-bit burst error-detecting code, the method comprising:aâ€”select values for n, k, and d, wherein n is the block length of the code in bits and k is the length of the information word in the code in bits and d is the number of adjacent error detection syndromes; bâ€”calculate the number of parity bits r=nâˆ’k; câ€”check to insure that râˆ’1 is less than or equal to d which is less than or equal to [(2r)âˆ’nâˆ’1]dâ€”construct an addition table for the nonzero elements of GF(2r) for a chosen minimal polynomial p(x) with the syndromes expressed in exponential notation, wherein GF is a Galois Field; eâ€”form the set S, the set S initially containing all nonzero syndromes and used as a reference for the rows and columns of the addition table; fâ€”form the sets H and D, the sets H and D each initially empty, wherein the set H contains error correction syndromes and the set D contains adjacent error detection syndromes; gâ€”add syndromes [0, 1, . . . , râˆ’1] to set H and delete syndromes [0, 1, . . . ., râˆ’2] from set S as well as their corresponding rows and columns from the addition table; hâ€”add syndromes [0+1, 1+2, . . . , (râˆ’2)+(râˆ’1)] to set D and delete them from set S and the addition table; iâ€”upon the number of elements in set D being less than d, find a syndrome that occurs most frequently in the addition table but is not a member of set D; jâ€”add the syndrome that occurs most frequently to set D; kâ€”delete the syndrome that occurs most frequently from set S; lâ€”delete the corresponding row and column of the syndrome that occurs most frequently from the addition table; mâ€”determine if the number of elements in set D is less than d; if so, return to step i and if not, continue with the following step; nâ€”replace all occurrences of syndromes not in set D, in the body of the addition table, with âˆ’1 to produce an adjacency matrix A; oâ€”use the adjacency matrix A to perform a path search for a path of length n beginning with vertex râˆ’1 and adding syndromes to set H and deleting them from set S as the path grows; pâ€”upon the path search terminating successfully, the set H comprises the parity check matrix H; qâ€”upon d being less than [(2r)âˆ’nâˆ’r], in the syndromes remaining in set S, there are detection syndromes that do not detect adjacent errors; and râ€”convert the columns of parity check matrix H from exponential to polynomial notation.