Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-09-26
2004-07-13
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S746000
Reexamination Certificate
active
06763492
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to transfer (i.e. transmission and/or storage) of digital signals. More specifically, the present invention relates to encoding of linear block codes.
2. Description of the Related Art
Digital signals are commonly used in applications such as voice, data, and video communications and image, data and document storage, processing, and archiving. Unfortunately, because storage media and transmission channels are not perfect, they tend to introduce errors into the digital information passing through them. In a storage medium, for example, errors may arise because of defects which prevent some or all of the digital signal from being properly stored, retained, or retrieved. In a transmission channel, errors may arise because of interference from another signal or variations in channel quality due to a fading process, for example.
To increase data robustness, an error detection scheme may be employed wherein a check value is calculated from the digital signal and transferred along with it. (In one common practice, the digital signal is divided into blocks, and a check value is calculated from and appended to each block before transfer. In other schemes, the digital signal and the check value may be interleaved and/or may have some other relative arrangement in time.) When the signal is retrieved or received, the check value calculation is repeated. If the check values calculated before and after the transfer agree, then the transferred signal may be assumed error-free. If the check values do not agree, then the signal may be assumed to contain at least one error. When a linear block code is used in such a calculation, the resulting check value is called a checksum, and when a cyclic code is used in such a calculation, the resulting check value is called a cyclic redundancy checksum or CRC. Depending on the type of code used and the number and/or type of errors encountered, it may be possible to correct such errors without retransmission of the digital signal.
For an (n, k) cyclic code C, k information symbols are encoded into an n-symbol code word. For example, a (48, 32) cyclic code produces a 48-bit code word comprising the 32 original information symbols and a 16-bit CRC. A cyclic code of this type may be uniquely defined by a generator polynomial G(X) of degree n−k having the form
G
(
X
)
=
1
+
(
∑
i
=
1
n
-
k
-
1
g
i
X
i
)
+
X
n
-
k
.
A checksum calculated according to such a code has a length of n−k bits. An exemplary format for an (n, k) code is shown in FIG.
1
.
Addition over the Galois field GF(
2
) reduces to a logical exclusive-OR (XOR) operation, while multiplication over this finite field reduces to a logical AND operation. For a cyclic code generated by a generator polynomial as described above and applied over GF(
2
), therefore, an encoder may be implemented using the logical circuit shown in FIG.
2
. In this figure, the g
i
represent the coefficients of the generator polynomial G(X), each of the (n−k) storage elements holds one bit value, and the contents of the storage elements are updated in unison (i.e. values are shifted into the storage elements at every clock cycle). During the first k shifts, the switch pulls are in the upper positions to allow the information signal to be loaded into the encoder (and passed through to the output if desired). For the next (n−k) shifts, the switch pulls are moved to the lower positions to allow the state of the encoder (i.e. the string of bits corresponding to the ordered contents of the storage elements) to be clocked out as the checksum signal.
If the generator polynomial is known during the design of the encoder, the circuit of
FIG. 2
may be simplified by omitting the i-th AND gate (for g
i
=0) or replacing it with a connection (for g
i
=1). For example, the code polynomial
G
(
X
)=
X
16
+X
15
+X
14
+X
11
+X
6
+X
5
+X
2
+X+
1
(as specified in, e.g., sections 2.1.3.4.2.1 and 2.1.3.5.2.1 of part
2
of the IS-2000 standard published by the Telecommunications Industry Association, Arlington, Va.) may be implemented with the logical circuit shown in FIG.
3
.
Although they have very low hardware requirements, using very little storage and only a few logic gates, serial encoder implementations as shown in
FIGS. 2 and 3
process only one bit of the input signal per clock period. Such performance may be unacceptably slow, especially for applications that involve real-time data streams (for example, communications applications).
Encoders that operate on more than one bit per cycle have been implemented by using precalculated lookup tables. In these implementations, a remainder for the current cycle is used as an index for choosing a value from a lookup table, and the chosen value is used to calculate a remainder for the next cycle. Although such an encoder processes multiple bits per cycle, it requires a lookup table whose size is related exponentially to the length of the remainder. Therefore, such implementations scale poorly and may not be suitable for applications that require both high speed and low storage consumption.
SUMMARY
In an apparatus according to an embodiment of the invention, a logic matrix receives an information signal and impulse responses that correspond to portions of the information signal. The logic matrix outputs a checksum that is based on a summation of at least two of the impulse responses.
REFERENCES:
patent: 5303245 (1994-04-01), Shikakura et al.
patent: 5491700 (1996-02-01), Wright et al.
patent: 5703887 (1997-12-01), Heegard et al.
patent: 5978956 (1999-11-01), Weng et al.
patent: 6029186 (2000-02-01), DesJardins et al.
patent: 6105158 (2000-08-01), Chen et al.
patent: 6195780 (2001-02-01), Dravida et al.
patent: 6263470 (2001-07-01), Hung et al.
patent: 6308295 (2001-10-01), Sridharan et al.
patent: 6336200 (2002-01-01), Wolfgang
patent: 6360348 (2002-03-01), Yang
patent: 0470451 (1992-02-01), None
patent: 0609595 (1994-08-01), None
patent: 94/15407 (1994-07-01), None
Hurt James Y.
Levin Jeffrey A.
Schlegel Nikolai
Chaudry Mujtaba
De'cady Albert
Godsey Sandra
Qualcomm Incorporated
Rouse Tom
LandOfFree
Method and apparatus for encoding of linear block codes 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 encoding of linear block codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for encoding of linear block codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3233411