Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-07-21
2003-05-06
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S752000, C714S798000, C375S145000, C375S149000, C340S870030
Reexamination Certificate
active
06560745
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates, in general, to error detection/correction and fault detection/recovery, and, in particular, to digital data error correction using forward correction by block code for determining synchronization.
BACKGROUND OF THE INVENTION
To encode a signal of a user-definable length using forward error correction, a user first determines the number of bits k of the signal that will be encoded per codeword. The variable k is often referred to as the number of information bits per codeword.
Next, the user determines the length n of the codewords. Each codeword is the same length. The length of the codeword determines the amount of redundancy that is added to the information bits. The values of the redundant bits are a function of the information bits and, therefore, provide information on the true value of the information bits. Therefore, the redundant bits may be used to determine the true value of the information bits and, therefore, correct the information bit if the information bit is not the true value. The amount of redundancy introduced into a codeword is proportional to the number of errors that may be corrected. An error in a codeword is a bit in the codeword that is not correct (i.e., a 0 when it should be a 1, or vice versa). Typically, errors are introduced into a codeword during the transmission of the codeword. The source of the error is often equipment malfunction or noise in the transmission channel. Greater redundancy provides greater information on the true value of the information bits and, therefore, provides lesser dependence on any single bit for the true value of an information bit. A lesser dependence on a single bit for the true value of an information bit increases the number of errors that can be withstood (i.e., corrected) by the codeword.
Next, the user selects a k by n generator matrix G. Procedures exist for each prior art encoding scheme for selecting a generator matrix once k and n have been established.
Next, the user selects k bits from the signal to be encoded and multiplies these bits by the generator matrix G to produce an n-bit codeword. If k is 3 and n is 6 then G is a 3×6 matrix, where 3 signal bits will be used to generate each codeword, and each codeword will be 6 bits long. In this example, 3 information bits are encoded to form a 6-bit codeword. So, the codeword contains 3 redundant bits that may be used to determine the true values of the 3 signal bits even in the presence of a certain maximum number of errors introduced into the codeword. For example, a signal to be encoded is 001010011100101110111, where k is 3, n is 6 and G is as follows.
G
=
[
1
0
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
1
]
The signal is then divided into 3-bit segments (i.e., 001, 010, 011, 100, 101, 110, and 111). Each segment is then multiplied by G to form the following 6-bit codewords, respectively: 001011, 010110, 01110101, 10001, 101110, 110011, and 111000.
The generator matrix G, which is based on k and n, sets the maximum number of errors that the codeword generated therefrom can withstand.
The bit location at which a codeword begins is referred to as a codeword boundary. The receiver that will receive an encoded signal must know where is the codeword boundary in order to properly identify the bits of each codeword. Once the codeword boundary is known then the codewords may be decoded to recover the unencoded signal.
A prior art method of determining codeword boundary is to insert a known bit pattern, or marker, between the codewords prior to transmission. The receiver, which must know beforehand what is the marker, checks the received transmission for occurrences of the marker and assumes that each occurrence indicates a codeword boundary. The codewords are then identified and decoded accordingly. A first disadvantage of this method is that adding a marker between each codeword requires more bits to be transmitted and, therefore, reduces the effective transmission rate of the codewords. For example, if a marker is equal to the length of a codeword then half of the bits transmitted correspond to markers and half of the bits transmitted correspond to codewords. So, the codeword transmission rate for this example is half that of transmitting codewords without markers. A second disadvantage of this method is that an error in a marker may cause a codeword boundary to not be recognized as such and, therefore, cause the received transmission to be decoded improperly. A prior art method of lessening the effect of the second disadvantage is to add error correction to the marker. Adding error correction to a marker increases its bit length and, therefore, further reduces the codeword transmission rate.
U.S. Pat. No. 4,389,636, entitled “ENCODING/DECODING SYNCHRONIZATION TECHNIQUE,” discloses a device for and method of synchronization that encodes each signal bit as a complementary-bit-pair. Encoding each signal bit as a complementary-bit-pair reduces the codeword transmission rate and does not achieve the maximum codeword transmission rate as does the present invention which does not encode each signal bit as a complementary-bit-pair. U.S. Pat. No. 4,389,636 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 4,959,834, entitled “WORD SYNCHRONIZATION SYSTEM AND METHOD,” discloses a device for and method of synchronization that calculates a syndrome, sends synchronization pulses, changes the phase of the received signal, and recalculates the syndrome if the first syndrome calculation is not as expected (i.e., zero). The present invention does not calculates a syndrome, send synchronization pulses, and change the phase of the received signal as does U.S. Pat. No. 4,959,834. U.S. Pat. No. 4,959,834 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,761,249, entitled “SYNCHRONIZATION ARRANGEMENT FOR DECODER/DE-INTERLEAVER,” discloses a device for and method of synchronization that requires the inclusion of periodic decoder synchronization signals in the received signal (i.e., markers). The present invention does not require the inclusion of a marker to indicate codeword boundary. U.S. Pat. No. 5,761,249 is hereby incorporated by reference into the specification of the present invention.
SUMMARY OF THE INVENTION
It is an object of the present invention to determine the codeword boundary of an encoded signal transmitted without marker bits for indicating codeword boundary.
It is another object of the present invention to determine the codeword boundary of an encoded signal transmitted without marker bits for indicating codeword boundary by calculating a dot product of at least one codeword and at least one vector of a dual of the code used to encode the signal.
It is another object of the present invention to determine the codeword boundary of an encoded signal transmitted without marker bits for indicating codeword boundary by calculating a dot product of at least one codeword and at least one vector of a dual of the code used to encode the signal even if the encoded signal includes more errors than the code was designed to withstand.
The present invention is a method of determining the starting bit position of a codeword (i.e., the codeword boundary) that does not require the use of marker bits to identify the codeword boundary.
The first step of the method is receiving a plurality of transmission bits. The transmission bits include at least one codeword.
The second step of the method is determining the dual code of a code used to generate the at least one codeword in the transmission bits.
The third step of the method is selecting a vector from the dual code, excluding an all-zeros vector.
The fourth step of the method is initializing n scoring variables S
z
each to zero, where 1≦z≦n.
The fifth step of the method is initializing i=1.
The sixth step of the method is initializing z=1.
The seventh step of the method is selecting n bits from the received transmission bits t
i
for processing, starting at bit positio
McCloskey Joseph P.
York Eric V.
De'cady Albert
Gandhi Dipakkumar
Morelli Robert D.
The United States of America as represented by the National Secu
LandOfFree
Method of identifying boundary of markerless codeword 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 of identifying boundary of markerless codeword, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of identifying boundary of markerless codeword will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3082614