Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1998-10-05
2001-08-28
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
Reexamination Certificate
active
06282691
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a cyclical redundancy check (CRC) coding system for a mobile data communication. More particularly, the invention relates to a CRC coding system for a mobile communication system with enhanced error detecting performance.
2. Description of the Related Art
In a high speed data transmission system in a digital car telephone system, a CRC coding method is employed. The conventional CRC coding method has been set forth in RCR STD-27D as a standard specification of a digital car telephone system defined by Research & Development Center for Radio Systems, Japan.
The CRC coding method set forth in RCR STD-27D has two kinds of CRC, i.e. CRC-16 and CRC-CCITT. In both CRC coding methods, information is input to a CRC encoder taking a most significant bit (MSB) of the data as a leading bit for adding CRC code from the MSB.
FIGS. 9 and 10
show a construction for realizing the conventional CRC coding system. On a transmission side, data is input to a CRC-16 encoder
210
from the MSB to add CRC-16 code and then to output to a CRC-CCITT encoder
220
. Then, transmission data is transmitted from the CRC-CCITT encoder
220
with adding CRC-CCITT code.
On a reception side, received data is input to the CRC-CCITT encoder
220
from the MSB. When all data are zero (0), judgment is made that there is no error. On the other hand, data eliminated CRC-CCITT code and CRC-16 code are input to the CRC-16 encoder
210
. If all data in the CRC-16 encoder
210
are zero (0), judgment is made that there is no error. Then, data eliminated CRC-16 code is taken as a received data.
Hereinafter, discussion will be given for conventional way of calculation of CRC-16 code.
Conventional procedure of calculation of CRC-16 code.
Respective bits to be transmitted are taken in sequential order from the MSB to be a
191
, a
190
, a
189
, . . . a
2
, a
1
, a
0
.
Respective bits derived by calculation are taken in sequential order from the MSB to be b
191
, b
190
, b
189
, . . . b
2
, b
1
, b
0
.
Respective bits of the CRC-16 thus derived are taken in sequential order from the MSB to be c
15
, c
14
, c
13
, . . . c
2
, c
1
, c
0
.
CRC-16 code can be derived through the following equation (1).
X
16
·
P
(
X
)
=
Q
(
X
)
·
G
(
X
)
+
R
(
X
)
P
(
X
)
=
a
191
X
191
+
a
190
X
190
⋯
+
a
1
X
+
a
0
Q
(
X
)
=
b
191
X
191
+
b
190
X
190
⋯
+
b
1
X
+
b
0
R
(
X
)
=
c
15
X
15
+
c
14
X
14
⋯
+
c
1
X
+
c
0
G
(
X
)
=
X
16
+
X
15
+
X
2
+
1
(
1
)
where, P(X) is a polynominal expression derived from data to be transmitted, Q(X) is a polynominal expression of a solution, R(X) is a polynominal expression of CRC-16, and G(X) is a CRC-16 generating polynominal expression.
From this, c
15
to c
0
can be derived by deriving b
191
to b
0
in sequential order from the following equation (2). It should be noted that calculation of a
191
to a
0
, b
191
to b
0
and c
15
to c
0
are all mod
2
(0+0=1+1=0, 0+1=0−1=1).
b
191
=
a
191
b
190
=
a
190
+
b
191
b
189
=
a
189
+
b
190
b
188
=
a
188
+
b
189
⋮
b
2
=
a
2
+
b
3
+
b
16
+
b
18
b
1
=
a
1
+
b
2
+
b
15
+
b
17
b
0
=
a
0
+
b
1
+
b
14
+
b
16
c
15
=
b
0
+
b
13
+
b
15
c
14
=
b
12
+
b
14
c
13
=
b
11
+
b
13
⋮
c
2
=
b
0
+
b
2
c
1
=
b
1
c
0
=
b
0
(
2
)
Accordingly, respective bits to be transmitted are expressed on the basis of the MSB by the following equation (3).
a
191
,a
190
,a
189
, . . . a
2
,a
1
,a
0
,c
15
,c
14
,c
13
, . . . , c
2
,c
1
,c
0
(3)
where c
15
to c
0
are result of the foregoing calculation.
In general, upon reception of data, due to external disturbance or so forth in the transmission zone, it is possible to cause the leading bit to drop out, or addition of extra bit.
In such case, in the conventional CRC coding method, data is received in a condition where the data appears bit shifted from the original data to make that no error is judged upon checking of code error, high. The reason is that shift registers are employed as encoders in CRC-16 and CRC-CCITT.
As one example, the conventional calculation method of CRC-16 code when bit shift in data generated by the CRC-16 encoder by drop out of the leading bit on the reception side, will be discussed hereinafter.
Conventional Calculation of CRC-16 code upon Occurrence of Drop out of One bit
When the data transmitted through conventional CRC-16 calculation causes drop out of the first one bit, the reception data on the reception side lacks a
191
and thus can be expressed by the following expression (4) on the basis of the MSB.
a
190
,a
189
,a
188
, . . . ,a
1
, a
0
,c
15
,c
14
,c
13
,c
12
, . . . ,c
1
,c
0
,e
15
(4)
where e
15
is the MSB of CRC-CCITT.
The foregoing expression (4) is then adapted to the equation for deriving CRC-16. It is assumed that solutions derived through calculation are b′
191
, b′
190
, b′
189
, . . . , b′
2
, b′
1
, b′
0
in sequential order from the MSB, and respective bits of the CRC-16 code derived are c′
15
, c′
14
, c′
13
, . . . , c′
2
, c′
1
in sequential order from the MSB. Thus, the following equation (5) is established.
R
′
(
X
)
=
X
16
·
P
′
(
X
)
-
Q
′
(
X
)
·
G
(
X
)
P
′
(
X
)
=
a
190
X
191
+
a
189
X
190
⋯
+
a
0
X
+
c
15
Q
′
(
X
)
=
b
191
′
X
191
+
b
189
′
X
190
⋯
+
b
1
′
X
+
b
0
′
R
′
(
X
)
=
c
15
′
X
15
+
c
14
′
X
14
⋯
+
c
1
′
X
+
c
0
′
G
(
X
)
=
X
16
+
X
15
+
X
2
+
1
(
5
)
where P′ (X) is a polynominal expression established from the received data, Q′ (X) is a polynominal expression of the solutions, R′ (X) is a polynominal expression of CRC-16 code, and G′ (X) is a CRC-16 generating polynominal expression.
When the following expression (6) is satisfied, recognition is made on the reception side that data is correct.
c′
15
=c
14
,c′
14
=c
13
,c′
13
=c
12
, . . . , c′
2
=c
1
,c′
1
=c
0
,c′
0
=e
15
(6)
When calculation is performed and the result of the conventional CRC-16 calculation method is added, and considering that a
191
=0, a result as expressed by the following equation (7) can be obtained.
Here, it should be noted that the reason why it is assumed that a
191
=0 is given, is that the condition that a
191
=0 is an essential condition since distinct cases where a
191
is added to respective bits of the solutions and respective bits of the CRC-16 code, and where a
191
is not added to respective bits.
b
191
′
=
a
190
=
b
190
+
b
191
=
b
190
+
a
191
=
b
190
b
190
′
=
a
189
+
b
191
′
=
(
b
189
+
b
190
)
+
b
190
=
b
189
b
189
′
=
a
188
+
b
190
′
=
(
b
188
+
b
189
)
+
b
189
=
b
188
b
188
′
=
a
187
+
b
189
′
=
(
b
187
+
b
188
)
+
b
188
=
b
187
⋮
b
2
′
=
a
1
+
b
3
′
+
b
16
′
+
b
18
′
=
(
b
1
+
b
2
+
b
15
+
b
17
)
+
b
2
+
b
15
+
b
17
=
b
1
b
1
′
=
a
0
+
b
2
′
+
b
15
′
+
b
17
′
=
(
b
0
+
b
1
+
b
14
+
b
16
)
+
b
1
+
b
14
+
b
16
=
b
0
b
0
′
=
c
15
+
b
1
′
+
b
14
′
+
b
16
′
=
(
b
0
+
b
13
+
b
15
)
+
b
0
+
b
13
+
b
15
=
0
c
15
′
=
b
0
′
+
b
13
′
+
b
15
′
=
b
12
+
b
14
=
c
14
c
14
&prim
Baker Stephen M.
Foley & Lardner
NEC Corporation
LandOfFree
CRC coding system and CRC coding method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with CRC coding system and CRC coding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CRC coding system and CRC coding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441665