Patent ID: 8438206

Claim:
A linear feedback shift calculation apparatus, into which input data is input, and which outputs output data, comprising: an L generation unit which generates q values of q 0 to q N−2 represented by: q k = { p 0 ( k = 0 ) p k + ∑ i = 0 k - 1 ⁢ q k - 1 - i × p i ( 1 ≤ k ≤ N - 2 ) Equation ⁢ ⁢ 35 (where, p 0 , p 1 , . . . , p N−1 , q 0 , q 1 , . . . , q N−2 belong to Galois field GF(2)) from coefficients p 0 to p N−2 among inputted coefficients p −1 to p N−1 (wherein, N is a natural number of 2 or more), and stores the q values of q 0 to q N−2 in a memory; and a matrix calculation unit which outputs the output data calculated from the output data b 0 to b N−1 represented by: ( b N - 1 b N - 2 ⋮ b o ) = L × ( U × ( a N - 1 a N - 2 ⋮ a 0 ) + p - 1 × ( a - 1 a - 2 ⋮ a - N ) ) Equation ⁢ ⁢ 36 and L = ( 1 0 … 0 0 0 q 0 1 0 … 0 0 q 1 q 0 1 0 … 0 ⋮ ⋱ ⋱ ⋱ ⋮ q N - 3 q N - 4 … q 0 1 0 q N - 2 q N - 3 … q 1 q 0 1 ) ⁢ ⁢ U = ( p N - 1 p N - 2 … p 2 p 1 p 0 0 p N - 1 p N - 2 … p 2 p 1 0 0 p N - 1 p N - 2 … p 2 ⋮ ⋱ ⋱ ⋱ ⋮ 0 0 … 0 p N - 1 p N - 2 0 0 … 0 0 p N - 1 ) Equation ⁢ ⁢ 37 from the q values q 0 to q N−2 read out from the memory, the coefficients p −1 to p N−1 and the input data a −N to a −1 , a 0 to a N−1 .