Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-09-08
2004-07-06
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06760880
ABSTRACT:
FIELD OF THE INVENTION
The present invention relater-to met hods and apparatus for calculating scalar products over Galois Field (GF2) in general, and for calculating a parity check of a binary vector, in particular, These scalar operations are employable in communication systems which employ coding techniques (e.g. block codes or convolutional coder) and synchronizaton mechanisms.
BACKGROUND OF THE INVENTION
A scalar product of two binary vectors over GF2 plays a crucial part in a variety of applications. such as error correcting codes, codes for synchronization, parity check, binary convolution and multiplication of polynomials over GF2.
A scalar product is defined as follows;
Let A=(a
1
, a
2
, . . . a
n
) and B−(b
1
, b
2
, . . . b
n
), where both A and B are binary vectors of length n.
Therefore, the resultant scalar product is: Z=(A,B)
2
Z
=
(
A
,
B
)
2
=
(
∑
i
=
1
n
⁢
⁢
a
1
⁢
b
1
)
⁢
⁢
mod2
mod2
where Z is the parity check of selected columns of binary vector A, and where binary vector B is used as a mask defining the selected columns. Where the binary code of B is defined as 0, the associated binary code of A is masked, and a parity check is not calculated. Where the binary code of B is defined as 1, a parity check of the associated binary code of A is calculated. As such, when B is defined as an all-ones vector, parity of the entire vector A is computed.
SUMMARY OF THE PRESENT INVENTION
It is an object of the present invention to provide a mechanism that computes a scalar product (SP) of two binary vectors of length n<=SIZE within one cycle, where n is the length of a first binary vector and SIZE is the length of a second binary vector. Typically, the second binary vector is a word of either 16, 20, 24, 32, 40. 48 or 56 bits, or any other length less than 56 bits.
Furthermore, if n>SIZE<2*SIZE then it is possible to perform the scalar product within 2 cycles by activating a special include zero switch. It is additionally noted that if n>2*SIZE, the scalar product is performed within
[
n
SIZE
]
×
3
/
2
⁢
⁢
cycles
,
where
[
n
SIZE
]
is a minimal integer equal to or greater than
n
SIZE
.
Furthermore, in several applications, such as convolutional codes or cyclic linear block codes, the information is represented as a polynomial of degree n>>SIZE.
The encoder generates the encoded data by multiplying it with generating polynomials of degree less or equal to SIZE. The present invention supports this computation with complexity of n cycles per generating polynomial,
A typical CPU supports bit by bit multiple input XOR operation, therefore, it takes n cycles to check the parity of a vector of length n. To overcome this drawback, in several applications external hardware is added. Another approach, for example in convolutional codes, is to implement the encoder as state machine.
There is therefore provided in a preferred embodiment of the present invention, a multiple input XOR for determining the parity of a vector.
There is additionally provided an apparatus for determining the parity of a vector, The apparatus includes a storage unit for storing an input vector of length N and a multiple input XOR for determining the parity of M bits of the input vector and for generating a parity bit. Alternatively, the apparatus further includes means for providing the bits of the input vector and the parity bit to the XOR, such that the parity of the entire input vector is determined.
Preferably the apparatus also includes means for generating an activation means, or switch, which considers the value of the parity bit, and dependent therefrom, activates conditional instructions. The apparatus may also includes an accumulator for storing a second vector and an input carry means. The input carry means, upon receipt of the parity bit, inputs the most significant bit from the accumulator into the least significant bit of the storage unit.
Preferably the apparatus further includes shift means for shifting the input vector one bit, within the storage unit, upon receipt of the most significant bit. In addition, preferably all of the means operate independently.
REFERENCES:
patent: 4313160 (1982-01-01), Kaufman et al.
patent: 4430737 (1984-02-01), Beranger et al.
patent: 4617625 (1986-10-01), Nagashima et al.
patent: 4626711 (1986-12-01), Li
patent: 4811344 (1989-03-01), Chauvel et al.
patent: 4996689 (1991-02-01), Samad
patent: 5040179 (1991-08-01), Chen
patent: 5155387 (1992-10-01), Fletcher et al.
patent: 5523707 (1996-06-01), Levy et al.
patent: 5548665 (1996-08-01), Gion et al.
patent: 5550766 (1996-08-01), Al-Zamil
patent: 5778241 (1998-07-01), Bindloss et al.
patent: 5894487 (1999-04-01), Levitan
patent: 5954836 (1999-09-01), Wang
patent: 6330702 (2001-12-01), King
Janusz Rajski et al “Test Data Decompression for Multiple Scan Designs With Boundary Scan” IEEE Transactions on Computers, vol. 47, No. 11, Nov. 1998.
Keren Osnat
Ofek Eli
Ceva D.S.P. Ltd.
Chung Phung M.
Eitan, Pearl, Latzer & Cohen Zedek LLP
LandOfFree
Scalar product and parity check does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scalar product and parity check, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalar product and parity check will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3235732