Arithmetic unit performing cyclic redundancy check at high...

Details Arithmetic unit performing cyclic redundancy check at high... Arithmetic unit performing cyclic redundancy check at high...

2001-01-26

2004-04-20

Dildine, R. Stephen (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C708S492000

Reexamination Certificate

active

06725415

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a CRC arithmetic unit for detecting a data transmission error by a CRC (cyclic redundancy check) system employed for transmitting a data string.
2. Description of the Background Art
In relation to communication of a data string, there is a method of determining whether or not the transmitted data string is normal by adding a check bit for an error detection check to an information bit to be transmitted and performing a prescribed operation in receiving. A method employing a parity bit is well known as a simple error detection system. In this method, a single parity bit is added in response to whether the number of “1” included in each transmitted data string is even or odd.
A cyclic redundancy check (hereinafter abbreviated as CRC) is a method enhanced in detectability. In the CRC, an operation with a generating polynomial is performed on an information bit to be transmitted.
A method of forming a CRC sign is briefly described. First, it is assumed that P(X) represents an information data string to be transmitted corresponding to an information bit, G(X) represents a generating polynomial, F(X) represents a transmitted data string and R(X) represents a remainder polynomial corresponding to a check bit. These are expressed in sign polynomials. In a sign polynomial, a binary number is expressed in a polynomial. For example, P(X)=“100 1011 0100 1011” is expressed as follows:
P
(
X
)=
X
14
+X
11
+X
9
+X
8
+X
6
+X
3
+X
1
+1
When the generating polynomial G(X) is equal to X
8
+X
7
+X
6
+X
4
+X
2
+1, the transmitted data string F(X) is obtained by the following expressions (1) to (3):
First, the information data string P(X) is multiplied by the high-order term X
8
of the generating polynomial G(X) for obtaining P′(X) as follows:
P
′(
X
)=
P
(
X
)×
X
8
  (1)
Then, P′(X) is subjected to mod2 division described later by the generating polynomial G(X) for obtaining the remainder polynomial R(X). It is assumed that “/” denotes the mod2 division described later.
R
(
X
)=
P
′(
X
)/
G
(
X
)  (2)
The obtained remainder polynomial R(X) is added to P′(X) for obtaining the transmitted data string F(X) as follows:
F
(
X
)=
P
′(
X
)+
R
(
X
)  (3)
FIG. 15
is a diagram for illustrating the mod2 division for obtaining the check bit from the information bit and the generating polynomial.
The operation of obtaining the check bit from the information bit when the generating polynomial G(X) is equal to X
8
+X
7
+X
6
+X
4
+X
2
+1 is described with reference to FIG.
15
. “1 1101 0101” corresponds to the generating polynomial, and the information bit is “100 1011 0100 1011”.
The number 0 of a bit number−1 in the generating polynomial is first added to the low order of the information bit. This processing corresponds to the operation shown in the expression (2).
The mod2 operation is performed on each bit of the generating polynomial in descending order. However, the mod2 operation generates no carry or negative carry dissimilarly to general division. In other words, the exclusive OR of each information bit and each bit of the generating polynominal is sequentially calculated. The most significant result is necessarily “0” and hence at least a single information bit is supplied to the lower result to match with the bit number of the generating polynomial. Referring to
FIG. 15
, symbol A denotes an intermediate result obtained in this stage.
The mod2 operation is thereafter similarly repeated, and terminated when the result is finally less than the bit number of the generating polynomial. The finally obtained remainder “00110001” is the obtained check bit. The operation of repeating the mod2 operation for obtaining the remainder is referred to as mod2 division in this specification.
The check bit obtained in the aforementioned manner is transmitted subsequently to the information bit when transmitting the data string. The receiving end confirms whether or not a transmission error occurs on the basis of the transmitted information and check bits.
FIG. 16
is a diagram for illustrating the operation for confirming whether or not a transmission error occurs.
Referring to
FIG. 16
, the mod2 division is performed on the data string transmitted with the check bit “0011 0001” added to the lower side of the information bit “100 1011 0100 1011” by the generating polynomial “1 1101 0101”. As to the mod2 division described with reference to
FIG. 15
, redundant description is not repeated.
When transmission is correctly performed, the remainder is zero and it is confirmable that no transmission error occurs.
FIG. 17
is a conceptual diagram showing the structure of a conventional CRC arithmetic unit
100
performing the division illustrated in
FIGS. 15 and 16
.
Referring to
FIG. 17
, the CRC arithmetic unit
100
includes XOR circuits
102
to
110
operating and outputting exclusive OR and registers
112
to
126
driven by a clock signal (not shown) for capturing and holding data.
The XOR circuit
102
operates and outputs the exclusive OR of a data string input in the CRC arithmetic unit
100
and a value held in the register
126
. The register
112
receives the output of the XOR circuit
102
and holds the same for a single clock period. The register
114
receives an output of the register
112
and holds the same for a single clock period. The XOR circuit
104
operates and outputs the exclusive OR of outputs of the registers
114
and
126
. The register
116
receives the output of the XOR circuit
104
and holds the same for a single clock period. The register
118
receives an output of the register
116
and holds the same for a single clock period.
The XOR circuit
106
operates and outputs the exclusive OR of the outputs from the registers
118
and
126
. The register
120
receives the output of the XOR circuit
106
and holds the same for a single clock period. The register
122
receives an output of the register
120
and holds the same for a single clock period. The XOR circuit
108
operates and outputs the exclusive OR of outputs from the registers
122
and
126
. The register
124
receives the output of the XOR circuit
108
and holds the same for a single clock period. The XOR circuit
110
outputs the exclusive OR of outputs from the registers
124
and
126
. The register
126
receives the output of the XOR circuit
110
and holds the same for a single clock period.
FIGS. 18
to
25
illustrate the process of operations in the CRC arithmetic unit
100
shown in FIG.
17
. The process up to the intermediate stage of the mod2 division shown in
FIG. 15
is described with reference to
FIGS. 18
to
25
.
Referring to
FIGS. 15 and 18
, the CRC arithmetic unit
100
is provided with the XOR circuits
102
to
110
in correspondence to positions where the bits of “1” of the generating polynomial are present. In other words, the structure of the CRC arithmetic unit
100
corresponds to the generating polynomial “1 1101 0101”.
First, it is assumed that all registers
112
to
126
initially hold “0”. Although not illustrated, it is general that values held in all registers
112
to
126
are initialized to “0” in response to a reset signal. While the register
126
holds “0”, the XOR circuits
102
to
110
output data received from preceding stages to subsequent stages intact. In other words, the CRC arithmetic unit
100
acts as a simple shift register until data “1” arrives at the register
126
.
After a lapse of a prescribed time, the registers
112
to
126
hold “1001 0110”. “1” is input in an input of the CRC arithmetic unit
100
.
Referring to
FIG. 19
, the registers
112
to
126
hold results operated in the XOR circuits
102
to
110
after a lapse of a single clock period. The next bit “0” is input in the input of the CRC arithmetic unit
100
. This state corresponds to the intermediate resul

Affiliated with

Also associated with

Rating

Arithmetic unit performing cyclic redundancy check at high... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arithmetic unit performing cyclic redundancy check at high..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic unit performing cyclic redundancy check at high... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3192730