Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-07-17
2004-11-16
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06820232
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a device and method for detecting errors in a CRC (Cyclic Redundancy Check) code, and more particularly to a device and method for detecting in a receiver any transmission errors in the CRC code, in a case that a transmitter transmits the CRC code generated by sequencing the parity bits, which are generated by using a generator polynomial in the reverse order, unlike the conventional manner, and by appending them to the message bits. The present application is based on Korean Patent Application No. 2000-66860, which is incorporated herein by reference.
Digital communication systems often use a method that adds the parity bits to the information bearing message bits to be transmitted in order to allow the receiver to detect transmission errors. In the receiver, the parity bits are checked alone or together with the message bits to determine whether transmission errors have occurred. Among the error detection methods using such parity bits, the CRC method is known as the most powerful method.
2. Description of the Related Art
FIG. 1
illustrates the structure of the conventional CRC (Cyclic Redundancy Check) code. Referring to
FIG. 1
, n bits of CRC code comprise k message bits (m
k−1
~m
0
) and n−k parity bits (p
n−k−1
~P
0
).
The CRC code can be represented by a certain polynomial, and the parity bits can also be represented by a polynomial using the remainder polynomial of the message bit polynomial divided by the generator polynomial.
The polynomial representation of the k message bits is
m
(
X
)=
m
0
+m
1
X
1
+m
2
X
2
+. . . +m
k−1
X
k−1
and, the polynomial representation of the generator polynomial for generating the parity bits is
g
(
X
)=
g
0
+g
1
X
1
+g
2
X
2
+. . . +g
n−k
X
k−1
and, the polynomial representation of the n−k parity bits is
p
(
X
)=
P
0
+p
1
X
1
+p
2
X
2
+. . . +P
n−k−1
X
n−k−1
Then, the CRC code can be expressed by
c
(
X
)=
X
n−k
m
(
X
)+
p
(
X
)
where, p(X)=X
n−k
m(X) mod g(X).
Such a CRC code method for detecting whether transmission errors have occurred divides the received CRC code by the generator polynomial and detects whether the remainder of the division is zero. This method for detecting transmission errors of the CRC code can be proved by the following equations.
As stated above, since p(X) is the remainder of X
n−k
m(X) divided by g(X), the following equation can be defined.
X
n−k
m
(
X
)=
g
(
X
)
Q
(
X
)+
p
(
X
)
Transposing p(X) to the left side, we have
X
n−k
m
(
X
)−
p
(
X
)=
g
(
X
)
Q
(
X
).
Here, since “−p(X)” equals “+p(X)” in the operations in the binary Galois Field unlike the general operations,
X
n−k
m
(
X
)+
p
(
X
)=
g
(
X
)
Q
(
X
).
In the above equation, since the left side equals c(X), the quotient and the remainder of c(X) divided by g(X) are Q(X) and “0,” respectively.
FIG. 2
illustrates a conventional device for detecting CRC code error using the stated principle. Referring to
FIG. 2
, the related device comprises a division unit
11
for dividing the received CRC code by the generator polynomial and a decision unit
13
for deciding the occurrence of errors by using the outputs from the division unit
11
. The division unit
11
comprises n−k one bit registers
11
a
, n−k multipliers
11
b
, and n−k exclusive-OR gates
11
c
. The decision unit
13
comprises a NOR gate
13
a
for NOR operation on the outputs from the registers
11
a
of the division unit
11
.
When a transmitter in the digital communication system transmits the CRC code bits (m
k−1
, m
k−2
, . . . , m
0
, P
n−k−1
, . . . , p
0
) having the structure shown in
FIG. 1
, the CRC code bits that have passed a proper channel are input to the registers
11
a
sequentially and each of the CRC code bits in the registers are shifted one position from left to right with every input. And, the multipliers
11
b
multiply the CRC code bits sequentially transferred via the right most register
11
a
by coefficient signal g
0
, g
1
, g
2
, . . . , g
n−k−1
of the generator polynomial, and each of the X-OR gates
11
c
performs bitwise exclusive OR operation on each resultant bit from each of the multipliers
11
b
and each of the CRC code bits that is subsequently input. After all the n bits are input to the registers
11
a
and processed by the aforementioned operations, the final remainder of the CRC code divided by the generator polynomial remain in the registers
11
a
. If no transmission errors have occurred, all the resultant contents of the registers
11
a
become “0s.” Thus, the decision unit
13
a
for performing NOR operations on the n−k input bits from the registers
11
a
provides an output “1,” only if the CRC code has no transmission errors. On the other hand, if the result of the entire NOR operations is “0,” the decision unit
13
a
decides that the CRC code has transmission errors.
Recently, a new method to generate the CRC code using the parity bits differently from the aforementioned method was suggested as a data transmission method in the Universal Mobile Telecommunication System (UMTS) related to the next generation mobile telecommunication, called an IMT-2000. That is, the UMTS adopts a new method for using the parity bits generated by sequencing the remainder bits of the message bits divided by the generator polynomial in the reverse order, unlike the conventional technique.
The new method will be explained in detail in the following.
FIG. 3
illustrates a structure of the CRC code in which the parity bits are added in the reverse order. The CRC code is transmitted in a sequence of m
k−1
, m
k−2
, . . . , m
0
, p
0
, . . . , p
n−k−1
. The CRC code can be expressed by a polynomial
c
(
X
)=
X
n−k
m
(
X
)+
p
⊥
(
X
)
where, taking p(X)=X
n−k
m(X) mod g(X), p
⊥
(X) is defined as
p
⊥
(
X
)=
X
deg p(X)
p
(
X
−1
).
However, the conventional error detection device can detect errors only in the conventional CRC code in which the parity bits are added in the normal order as illustrated in FIG.
1
. The conventional error detection device cannot detect transmission errors in the new CRC code in which the parity bits are added in the reverse order as illustrated in
FIG. 3
, because the remainder of the new CRC code polynomial c(X) divided by the generator polynomial g(X) does not become “0” in the conventional device. Accordingly, a need exists for detecting the transmission errors in the CRC code having the reverse ordered parity bits.
SUMMARY OF THE INVENTION
The object of the present invention is to provide a device and method for detecting transmission errors of the received CRC code in which a parity bit stream is added in reverse order.
In accordance with one aspect of the present invention to accomplish the object, there is provided a device for detecting errors in the CRC code comprising a switch unit for sequentially receiving the CRC code having message bits and reverse ordered parity bits appended to the message bits and for switching the message bits and the parity bits to be transferred separately; a division unit for receiving the message bits transferred via said switch unit and for dividing the message bits by a parity bit generator polynomial to obtain a remainder; a buffer unit for receiving the parity bits transferred via said switch and for buffering the parity bits sequentially; a comparison unit for comparing the remainder bits from said division unit with the parity bits from said buffer unit; and a decision unit for deciding whether transmission errors have occurred in the CRC code on the basis of the results from said comparison unit.
The comparison unit preferably comprises a plurality of X-OR gates for comparing the remainder bits with the parity b
Choi Sung-han
Kim Jae-hong
Kong Jun-jin
Chase Shelly A
De'cady Albert
Samsung Electronics Co,. Ltd.
LandOfFree
Device and method for detecting errors in CRC code having... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for detecting errors in CRC code having..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for detecting errors in CRC code having... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3359308