Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-07-01
2001-01-09
DeCady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S746000, C714S751000, C714S755000
Reexamination Certificate
active
06173431
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to packet data communication systems and, in particular, to transmitting and receiving information packets using multi-layer error detection.
BACKGROUND OF THE INVENTION
Packet data communication systems are known in both the land mobile and cellular environments. In the land mobile environment, the packet data system includes a packet router, a central controller, a plurality of base sites, and a plurality of communication devices (e.g., mobile radios, portable radios, or wireless data modems). In the cellular environment, the packet data system includes a packet router, one or more base site controllers, a plurality of base sites, and a plurality of communication devices (e.g., cellular telephones).
In a typical land mobile packet data transmission, the data packet is routed from a land user to a communication device via communication protocols that reside on several so-called communication protocol layers. In accordance with the Open Systems Interconnection (OSI) nomenclature, a first protocol layer (layer
1
) comprises a physical protocol, such as T1 channel framing. A second protocol layer (layer
2
) typically adds a header or trailer containing error correction or detection information to the data allowing the communication device to correct or detect bit errors incurred during the transmission of the packet from a base site. A third protocol layer (layer
3
) typically adds a header containing packet routing information (e.g., the appropriate Internet Protocol (IP) address for the communication device) to the data. A fourth protocol layer (layer
4
) typically includes an indication of the number of packets containing the data in the packet data communication and a sequential ordering of the packets. Finally, upper protocol layers (layer
5
and above) contain the actual data in the packet.
Data messages transmitted by packet data techniques are typically split into fragments. Each fragment is the information that is transmitted in a packet. The fragments are in turn split into a sequence of data blocks and each block, as well as the entire fragment, may then be individually protected against transmission errors.
Errors in the transmission of data can arise from many sources, such as adjacent channel and co-channel interference, fading, and undesired distortion in a sending device's transmitter and/or a receiving device's receiver. The result of the introduction of errors is a demodulated bit stream at the receiving communication device (data recipient) that is different from the bit stream that was modulated and transmitted by the sending communication device (data source). One method used to combat this problem is to include enough redundant information along with each block of data to allow the data recipient to deduce that an error occurred and to request a retransmission of either a particular data block or an entire message. The redundant information, or error detection code, is interleaved among the data blocks in communication protocol layer
2
. In some communication systems, error detection followed by retransmission is preferred to error correction because it is more efficient (i.e., much less overhead is consumed in sending an error detection code and retransmitting erroneous data blocks than is required by an error correction code).
There are many known techniques for generating an error detection code. One such technique is the addition of parity bits. Parity bits indicate whether the sum of a predesignated string of bits is odd or even. If the bits sum to an even number and the associated parity bit indicates an odd number, then an error is indicated and the data recipient requests retransmission of the block. However, this technique facilitates the detection of errors in an odd number of bits only. That is, with parity bit error detection, if an even number of bits are incorrect, then an error will not be detected. Another known technique for generating an error detection code is a cyclic redundancy check (CRC) code (also known as a polynomial code). A CRC code treats a bit string as though it is a coefficient list for a polynomial, each coefficient being either a 0 or a 1. Thus, a data block of ‘m’ bits can be thought of as a coefficient list for an ‘m−1’ degree polynomial, the highest order term being x
m−1
and the lowest order term being x
0
. For example, the bit stream 10101 equates to the polynomial x
4
+x
2
+x
0
.
When using a CRC code, the data source and the data recipient must agree upon a generator polynomial, G(x), of degree ‘g−1’ in which the high- and low-order bits are ones and the intervening bits are a combination of zeros and ones. The generator polynomial G(x) can be selected in accordance with known techniques so as to maximize its error detection rate. If the data block has ‘m’ bits and can be represented by the polynomial M(x) (degree ‘m−1’), then the CRC is a predesignated number of bits (‘k’ bits) appended to the lower end of the data so that it now contains m+k bits and corresponds to a polynomial, P(x), that is of order ‘(m+k)−1.’ The appended bits are typically referred to as a checksum. Standard practice is to use a checksum of 16 or 32 bits (i.e., k=16 or 32). The additional k bits are selected so that the new polynomial, P(x), is perfectly divisible by G(x) using modulo 2 arithmetic. Therefore, the additional k bits are selected such that m+k>g. If a non-zero remainder results when the data recipient divides the appended data block by G(x), then an error is indicated and retransmission is requested.
Wireless communications present greater opportunity for random channel error than do wireline communications and packet data transmissions are typically error intolerant. Thus, the problem with using merely a single CRC code per data block is that it would require too lengthy a checksum (i.e., it would consume an undesirable amount of overhead) to achieve the error detection rate required for wireless communication purposes. Thus, for wireless communications to approach the precision of wireline communications, a better error detection technique than a single CRC code per data block is required. The Telecommunication Industry Association (TIA) has proposed an improved error detection scheme in the publication entitled “TIA/EIA Standard, Project 25 FDMA Common Air Interface New Technology Standards Project Digital Radio Technology Standards,” TIA/EIA-102.BAAA, published by the Telecommunication Industry Association in May 1998.
The TIA proposes that each individual data block in the packet contain 16 octets of data and two octets of numbering and CRC information. If an error is detected in an individual block, then a retransmission of that block can be requested. This is known as selective automatic retransmission request (SARQ). The TIA further proposes that there be a four octet CRC parity check (i.e., a message CRC) covering the data of the entire packet that would be included in the last four octets of the last data block. Polynomial division requires that the division be undertaken starting with the highest order factors and sequentially progressing down to the lowest order factors. Determination and confirmation of the message CRC code requires that all data blocks be sequentially ordered, so that data blocks received either out of order or with errors would terminate all further determination of the CRC code. This can be an especially significant problem for wireless communication systems, where the data blocks of a packet are not necessarily correctly received in sequential order. The result could be a potential computational load placed on the data processor if message CRC code computations are deferred and a potential processing delay in computing the message CRC while awaiting retransmitted data blocks. Deferred CRC code computations can create processor utilization spikes and can introduce a significant delay in the sending of a message acknowledgment back to the sender.
Therefor
Crilly Daniel C.
De'cady Albert
Jacobs Jeffrey K.
Lamarre Guy
May Steven A.
LandOfFree
Method and apparatus for transmitting and receiving... 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 transmitting and receiving..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for transmitting and receiving... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2509974