Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-08-08
2004-05-18
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S752000
Reexamination Certificate
active
06738946
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to the field of packet communication, and, more particularly, to using a packet frame-check sequence (FCS) to convey information.
A common error detection technique that may be used in packet communication networks is known cyclic redundancy check (CRC). This technique may be explained as follows: Given a k-bit frame or message, a transmitter generates an n-bit sequence, known as a frame-check sequence (FCS), so that the resulting packet, consisting of k+n, bits is exactly divisible by some predetermined number. A receiver then divides the incoming packet by the same number and, if there is no remainder, assumes that there was no error.
Principles of the basic CRC algorithm may be expressed mathematically as follows: Let I(x) by a polynomial representing the message to be transmitted and let G(x) be a generating polynomial of degree n for the CRC algorithm. Typically, I(x) is multiplied by x
n
to left shift the message to make room for the n-bit FCS, which is denoted by R(x), at the low order of the packet. The relationship between I(x), G(x), and R(x) may expressed as set forth in Equation 1:
(
x
n
)I(
x
)=
Q
(
x
)
G
(
x
)+
R
(
x
), EQ. 1
where Q(x) is the quotient that results from dividing (x
n
)I(x) by G(x). The product Q(x)G(x) may be added to both sides of Equation 1, which yields Equation 2 below:
R
(
x
)=(
x
n
)I(
x
)+
Q
(
x
)
G
(
x
). EQ. 2
Note that Q(x)G(x)+Q(x)G(x) equals zero as any binary number added to itself is zero for the case of finite field coefficients. Equation 2, however, may be rewritten as a statement of congruence as set forth in Equation 3:
R
(
x
)=(
x
n
)I(
x
) mod
G
(
x
). EQ. 3
Thus, the FCS R(x) is given by the remainder that results from the division of the left shifted message polynomial (x
n
)I(x) by the generator polynomial G(x).
Conventional packet communication systems have used the FCS to convey information, such as an address or “color code.” A color code may be a code used to identify packets that are intended for multiple receiving stations. In this regard, a first group of receiving stations may accept packets encoded using a first color code, a second group of receiving stations may accept packets encoded using a second color code, etc. A transmitting station may append an address or color code to the high-order end of a message to create an extended message. The CRC algorithm may then be used to compute the FCS for the extended message. The FCS may be appended to the low-order end of the extended message to prepare the extended message for transmission. Before transmitting the extended message, however, the address or color code is removed from the high-order end of the extended message leaving the original message and the FCS computed for the extended message. A packet comprising the original message the FCS computed for the extended message may then be transmitted to one or more receiving stations.
Upon receipt of the packet at a receiving station, the receiving station may append its own address or accepted color code at the high-order end of the packet. The receiving station may then use the CRC algorithm to determine if the packet is in congruence with the CRC generator polynomial. If the packet is in congruence with the CRC generator polynomial, then the receiving station may presume that the transmitting station has addressed or color coded the packet for it. On the other hand, if the packet is not in congruence with the CRC generator polynomial, then the receiving station may presume that the transmitting station has addressed or color coded the packet for another receiving station or that the packet has been corrupted with a channel error. In this case, the packet may be discarded. Alternatively, conventional receiving stations may compute the FCS for the packet after appending their own address or accepted color code at the high-order end of the packet. If the computed FCS matches the FCS transmitted with the packet, then a receiving station may accept the packet, otherwise, the receiving station may discard the packet. In this manner, a packet may carry address or color code information for the packet implicitly in the FCS without increasing the size of the message field or adding one or more new information fields to the packet.
SUMMARY OF THE INVENTION
According to embodiments of the present invention, methods, communication devices, communication systems, and computer program products may be provided for communicating information via a frame-check sequence having an information block associated therewith. For example, one or more information blocks may be provided and respectively associated with one or more information block frame-check sequences. A message for transmission may be provided and a message frame-check sequence may be computed based on the message. One of the information blocks may also be selected for transmission along with the message. Rather than constructing a packet that includes both the selected information block and the message, however, the information block frame-check sequence that is associated with the selected information block is added to the message frame-check sequence to compute a transmit frame-check sequence. A packet comprising the message and the transmit frame-check sequence may then be transmitted.
In accordance with further embodiments of the present invention, the associations between the one or more information blocks and the one or more information block frame-check sequences are also provided at a receiver where the packet is received. Once received, the packet may be divided by a generator polynomial to determine whether any remainder results. If the remainder is non-zero, then a determination may be made whether remainder corresponds to any of the one or more information block frame-check sequences. If the remainder does correspond to one of the information block frame-check sequences, then the information block associated with the information block frame-check sequence that corresponds to the remainder may be processed as received information.
The present invention takes advantage of the principles of linearity and superposition inherent in the basic cyclic redundancy check (CRC) algorithm. Advantageously, the frame-check sequence for an information block may be added to the frame-check sequence for a message to thereby encode the information block into the packet. When the packet is received, a CRC operation may be performed, which results in a remainder corresponding to the frame check sequence for the encoded information block. Associations may be developed a priori between the one or more information blocks and their frame check sequences. Moreover, these associations may be stored, for example, in a data structure, such as a table. The remainder may thus be used to index the table and recover the encoded information block.
In accordance with further embodiments of the present invention, if dividing a received packet by the generator polynomial does not result in any remainder, then the receiver may presume that an information block has not been encoded in the packet and, therefore, only the message is processed as received information. Thus, broadcast packets (i.e., packets that are not specifically addressed or color coded) may be received and processed after performing a single CRC operation.
The present invention may decode packets from an information stream that includes both broadcast packets and packets that are addressed or color coded for specific receivers without performing multiple CRC analysis operations. That is, as discussed hereinabove, if dividing a received packet by the generator polynomial results in a non-zero remainder, then that remainder may be used, for example, to index a data structure in which information blocks are associated with frame check sequences. By determining which, if any, of the one or more information block frame check sequences corresponds to the remainder, the associated inform
Chaudry Mujtaba
Myers Bigel Sibley & Sajovec P.A.
Telefonaktiebolaget L.M. Ericsson
Tu Christine T.
LandOfFree
Methods, communication devices, and computer program... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods, communication devices, and computer program..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, communication devices, and computer program... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3227574