Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-07-31
2004-06-22
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S761000
Reexamination Certificate
active
06754871
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates generally to the field of data communications error correction and, in particular, to a method and apparatus for decoding shortened cyclic codes using error trapping.
2. Description of Related Art
In a (wireless) communications system, control signaling information is encoded and transmitted using control channel messages.
One specific wireless standard specification in widespread use is the Global System Mobile (GSM) specification. GSM defines a number of control channel messages, including: FACCH, SACCH, SDCCH, AGCH, PCH, and BCCH. These 184-bit control channel messages are encoded with 40 parity check-bits, which are generated by a shortened binary cyclic block code belonging to, for example, the family of so-called Fire codes. These codes are defined in ETS 300909 (GSM 05.03 version 5.5.1): October 1998—using the generator polynomial:
G
(
X
)=(
X
23
+1)*(
X
17
+X
3
+1).
The large number of parity check-bits virtually guarantees that a noise-corrupted signaling message will be detected and discarded by the base station.
The 40 parity check-bits generated by the Fire code can also be used to correct a single burst error up to 12 bits in length. Since signaling messages are interleaved over 4 or 8 bursts, the Fire code decoder could effectively correct error bursts of length 48 to 96 bits occurring in the air channel due to the diverse effects of signal interference. Since the 456 bits of a convolutionally encoded message are convolutionally decoded after deinterleaving and before the Fire code decoding procedure, a statistically significant percentage of signaling messages subject to error bursts can be completely recovered by the Fire code decoding procedure.
The error burst correction procedure is more than two orders of magnitude more computationally complex than the procedure for error detection. See (i) W. W. Peterson,
Error
-
Correcting Codes
, MIT Press, Cambridge, Mass, 1961 and (ii) R. T. Chien, “Burst-Correction Codes with High-Speed Decoding,” EEEE Transactions on Information Theory, IT(15), Issue 1, pp. 109-113, January 1969. Implementation of the Fire code decoder in real-time, therefore, has not been considered practical in consideration of other base transceiver stations (BTS) uplink burst processing requirements, such as demodulation, equalization, and convolutional error decoding.
The generator polynomial of a Fire code is expressed as the product of two polynomials G(x)=(x
2t−1
−1)*p(x), where the polynomial p(x) is characterized by a periodicity factor r
0
. A code using G(x) is able to correct any single burst error less than or equal to ‘t’ bits long.
Fire codes are represented by the notation F[n,k], where n is the number of coded bits, k is the length of the data to be coded, and (n−k) is the number of parity-check bits. The code can be shortened in length for a specific coding application by subtracting b bits from both the information word and its related code word to obtain the Fire Code F[N,K]=F[n−b,k−b].
In all of the following, for illustrative purposes, we shall refer to the case of the generator polynomial of the shortened Fire code F[224,184] specified in the aforementioned ETSI/GSM Standard, G(X)=(X
23
−1)*(X
17
+X
3
+1), which can correct a single burst error up to t=12 bits long. The polynomial (X
17
+X
3
+1) has a periodicity factor r
0
=(2
17
−1)=131,071.
A cyclic code (e.g., Fire code) decoder error correction procedure is based on a fast error-trapping decoder for Fire codes first taught by Peterson and refined by Chien (see citations above). There, the error-trapping decoder includes two error syndrome shift registers: an error-pattern register and an error location register. The error-pattern register is based on the factor (X
23
+1) of the generator polynomial G(X)=(X
23
+1)*(X
17
+X
3
+1), and the error-location register is based on the factor (X
17
+X
3
+1).
In the Chien method, the data is first shifted into both registers. If an error is detected and determined to be correctable, the error correction procedure consists of the following steps:
1. Compute the number of ‘0’ bits to be shifted into the first error syndrome register, the error-pattern register, until the burst error pattern is trapped in the ‘t’ low order stages of this register. The number of required shifts is computed to be &lgr;
1
.
2. Compute the number of ‘0’ bits to be shifted into the second error syndrome register, the error-location register, until the contents in the ‘t’ low-order stages matches the burst error pattern trapped in step 1. The number of required shifts is computed to be &lgr;
2
.
3. Use &lgr;
1
and &lgr;
2
as inputs to a set of equations described in R. T. Chien, “Burst-Correction Codes with High-Speed Decoding,” IEEE Transactions on Information Theory, IT(15), Issue 1, pp. 109-113, January 1969 and U.S. Pat. No. 5,381,423 by E. Turco, Issued on Jan. 10, 1995 (“Turco”) to compute the location of the burst error in the original data.
4. Use the error pattern trapped in step 1 to correct the burst error beginning at the location computed in step 3.
However, the Peterson and Chien fast trapping decoder does not explicitly address the requirements for dealing with a shortened Fire code. The GSM Fire code has been shortened to N=224 bits in length (i.e., K=184 bit control channel message plus 40 parity bits). The original length of the code corresponds to G(X)=(X
23
+1)*(X
17
+X
3
+1) is n=23*(2
17
−1)=3,014,633 bits. See S. Lin, D. J. Costello, Jr.,
Error Control Coding: Fundamentals and Applications
, p. 261, Prentice-Hall Publishing, Englewood Cliffs, N.J., 1983. Thus, the code has been shortened by 3,014,633−224=3,014,409 bits. In order for a shortened cyclic code decoder's syndrome registers to be properly initialized, in addition to shifting-in the data and parity bits, it is also necessary to shift in an additional number of ‘0’ bits equal to the number of shortened bits. This would require an additional 3,014,409 ‘0’ bits to be shifted into the syndrome registers.
Turco addresses the issue of shifting in the large number of ‘0’ bits by teaching that it is not necessary to shift the shortened zero (‘0’) bits into both the error-location and error-pattern registers. Instead, the shortened zero bits are only shifted into the error-location register. The number of zero bits to be shifted is equal to (r
0
−N+1)=130,848 bits.
Once the error burst pattern and location have been identified, Peterson, Chien, and Turco solve a set of equations, as described above in step 3, to locate where the error burst resides in the original data.
SUMMARY OF THE INVENTION
In the present invention, it is not necessary to perform step 3 in the error correction procedure proposed by (i) W. W. Peterson,
Error
-
Correcting Codes
, MIT Press, Cambridge, Mass., 1961 and (ii) R. T. Chien, “Burst-Correction Codes with High-Speed Decoding,” WEEE Transactions on Information Theory, IT(15), Issue 1, pp. 109-113, January 1969 and described by Turco in U.S. Pat. No. 5,381,423, issued Jan. 10, 1995. Nor is it necessary to use the value corresponding to &lgr;
1
in the Chien method to compute the location of the error burst. Rather, in the present invention, the location of the error burst is computed directly from the value &lgr;, which corresponds to the value &lgr;
2
in step 2 of the Chien procedure.
According to the principles of the present invention, a method and apparatus are used for correcting error bursts in a communication system using shortened cyclic codes, such as shortened Fire codes. Data is loaded into a first error syndrome register and a second error syndrome register. The data in the registers may be evaluated to determine if the data bits contain a correctable error. S
Huang Wenfeng
Kaiser Daryl
Pines Howard
Sayers Ian
Chung Phung M.
Cisco Technology Inc.
Hamilton Brook Smith & Reynolds P.C.
LandOfFree
Method and apparatus for using fire decoder to correct burst... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for using fire decoder to correct burst..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for using fire decoder to correct burst... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3363339