Patent ID: 6560746
Filing Date: 2003-05-06
Classification: H03M

Abstract:
A method for generating a parallel CRC generation circuit for parallely generating a CRC code of length N defined as a CRC polynomial (CRC)CRC=anxN+aNâˆ’1xNâˆ’1+ . . . anxn+ . . . a1x1+a0x0 where aN=a0=1 and the coefficients an are 0, 1 depending on the CRC code to be formed, parallely for a number T of input bits of a data stream, comprising the following steps:d) determining coupling groups in defining a coupling of input register output lines of an input register means (I) having T input registers I0, I1, . . . It . . . , ITâˆ’1 for simultaneously storing said T input bits, each input register having an output line I(0), I(1), . . . I(t) . . . , I(Tâˆ’1), and output register output lines of an output register means (C) having N output registers C0, C1, . . . Cn . . . , CNâˆ’1 for simultaneously storing said CRC code, with input lines of a number N of XOR gates XOR0, XOR1, . . . XORn . . . XORNâˆ’1 each having an output connected to a respective input line of said output registers and input lines being coupled with a predetermined number of said input register output lines and a predetermined number of said output register output lines; â€ƒwherein said step of determining comprises the following steps: e1) storing in a memory a matrix CT with N columns and T+1 rows: wherein the row elements ct0,0, ct0,1, . . . ct0,n . . . . ct0,Nâˆ’1 in row 0 respectively store the index of the output register output lines C0(0), C1(0), . . . Cn(0) . . . CNâˆ’1(0); and wherein the column elements for columns numbers n for which an=0 store an arbitrary non-read value indicating that this value is not to be considered for forming of coupling groups and column numbers n for which an=1 store the following value pair: ctT,n=iT-1=(I&af;(T-1),CN-1&af;(T-1))&it;&NewLine;&it;ctT-1,n=iT-2=(I&af;(T-2),CN-1&af;(T-2))&it;&NewLine;&it;â€ƒ&it;&vellip;&it;&NewLine;&it;ctt,n=it-1=(I&af;(t-1),CN-1&af;(t-1))&it;&NewLine;&it;â€ƒ&it;&vellip;&it;&NewLine;&it;ct1,n=i0=(I&af;(0),CN-1&af;(0))(2)where the first value in said pair denotes an input register output line, said second value in said pair denotes an output register state parameter and the value CNâˆ’1(0) denotes the output line of the output register output line CNâˆ’1; e2) determining the index of input register output lines and the index of output register output lines for each of said N XOR gates XOR0, XOR1, . . . XORn, . . . XORNâˆ’1 as follows: e21) selecting a number n[0, Nâˆ’1] of an XOR gate; e22) reading the element pair ctT,n from the matrix CT and all element pairs arranged in a diagonal direction therefrom for decreasing row and column numbers and grouping them in a coupling group gn; e23) if the coupling group gn comprises output register state parameters CNâˆ’1(t) With tâ‰ 0, reading element pairs CttNâˆ’1 with tâ‰ 0 corresponding to said output register state parameters and all elements pairs arranged in a diagonal direction therefrom for decreasing row and column numbers and replacing the output register state parameters in the coupling group with these values; e24) repeating said reading out step e23 until no further output register state parameters exist in said coupling group gn and cancelling pairs of identical input register output line indexes and identical output register output line indexes in said coupling group either at intermediate stages of the replacement or after all output register state parameters have been replaced; and e25) repeating steps e21-e24 for all N XOR gates to form N coupling groups; e26) wherein each coupling group gn for each XOR gate indicates the indices of the input register output lines and the output register output lines to be connected to the input of the respective XOR gate.