Sign In to Follow Application
View All Documents & Correspondence

Method And Apparatus For Error Detection In A Communication System

Abstract: A method processes a data packet in a first sequence of disjoint original segments of the same length. The method includes modifying a first of the original segments of the first sequence by modifying one or more symbols therein. A start of the data packet is located in the first of the original segments and is positioned after a first digital data symbol therein. The method also includes modifying a last of the original segments of the first sequence by modifying one or more digital data symbols therein. An end of the data packet is located in the last of the original segments and is located before the last digital data symbol therein. The method also includes determining a remainder sequence by effectively performing a polynomial division on a second sequence of disjoint segments that are derived from the first sequence. Each segment of the second sequence corresponds to and is derived from one of the original segments of the first sequence. The segments of the second sequence have the length of the original segments of the first sequence. A first of the derived segments of the second sequence is the modified first of the original segments. A last of the derived segments of the second sequence is derived from the modified last of the original segments.

Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence

Patent Information

Application #
Filing Date
11 May 2012
Publication Number
08/2014
Publication Type
INA
Invention Field
COMMUNICATION
Status
Email
remfry-sagar@remfry.com
Parent Application

Applicants

ALCATEL LUCENT
3, AVENUE OCTAVE GREARD, F-75007 PARIS

Inventors

1. ADRIAAN, J. DE LIND VAN WIJNGAARDEN
24 FIRST STREET, NEW PROVIDENCE, NJ 07974
2. ANDREAS, BERNHARD ZOTTMANN
BRESLAUER STR. 7, 91207 LAUF

Specification

METHOD AND APPARATUS FOR ERROR DETECTION IN A COMMUNICATION SYSTEM BACKGROUND Field of the Invention This invention relates to detecting transmission related errors in a packet-based communication system. Discussion of Art This section introduces various aspects that may aid the reader in obtaining a better understanding of various aspects of the inventions and should not be understood to include statements about what is prior art or what is not prior art. One goal of communication systems is to ensure that messages received by intended recipients are unaltered copies of the transmitted messages. For that reason, communication systems often employ error detection techniques that enable a recipient to determine whether a received message was altered during transmission. One technique for detecting channel-induced message errors is based on a cyclic redundancy check (CRC) code. A CRC code typically transforms a sequence of digital data symbols, e.g., representing a data message, to produce a sequence of digital check symbols. The sequence of digital check symbols is transmitted with the sequence of digital data symbols and a recipient uses the sequence of digital check symbols to evaluate whether the received sequence of digital data symbols is the same sequence that was originally transmitted. Some systems generate such a sequence of digital check symbols and detect transmission errors from the transmitted sequence of digital check symbols by using a feedback shift register. For example, a binary CRC code can be implemented with a shift register that is controlled by feedback via exclusive-OR (XOR) logic. The contents of memory elements of the shift register typically correspond to a remainder sequence that is produced by the division of the sequence of digital data symbols by a fixed generator polynomial. The remainder sequence is typically appended to the end of the sequence of digital data symbols for transmission to recipients of the data packet. In such systems, the remainder sequence is typically serially computed on a bit-by-bit basis prior to transmission of the data packet. SUMMARY One embodiment is a first method of processing a data packet that is located in a first sequence of disjoint original segments. Each original segment of the first sequence has the same length. The first method includes modifying a first of the original segments of the first sequence by modifying one or more symbols therein. A start of the data packet is located in the first of the original segments and is positioned after a first digital data symbol therein. The first method also includes modifying a last of the original segments of the first sequence by modifying one or more digital data symbols therein. An end of the data packet is located in the last of the original segments and is located before the last digital data symbol therein. The first method also includes determining a remainder sequence by effectively performing a polynomial division on a second sequence of disjoint segments that are derived from the first sequence. Each segment of the second sequence corresponds to and is derived from one of the original segments of the first sequence. The segments of the second sequence have the length of the original segments of the first sequence. A first of the derived segments of the second sequence is the modified first of the original segments. A last of the derived segments of the second sequence is derived from the modified last of the original segments. In some embodiments of the first method, each derived segment that does not include the start or end of the data packet may be equal to the corresponding one of the original segments. In any embodiments of the first method, the modifying steps may include masking portions of the original segments outside of the data packet such that said portions will contribute in a predetermined amount to the remainder determined by the polynomial division. In any embodiments of the first method, the modifying a first of the original segments may include modifying symbols at the start of the data packet. In some such embodiments, the modifying steps may include masking portions of the original segments outside of the data packet such that said masked portions will contribute in a predetermined amount to the remainder determined by the polynomial division. In any embodiments of the first method, the modifying of a last of the original segments may modify symbols at the end of the data packet. In some such embodiments, the modifying steps may include masking portions of the original segments outside of the data packet such that said masked portions will not contribute to the remainder determined by the polynomial division when a cyclic redundancy check of the data packet vanishes. In any embodiments of the first method, the first method may further include producing a third sequence by performing a symbol-by-symbol subtraction of a sequence of symbols from the first sequence such that a data packet located in the third sequence becomes a valid codeword of an error control code that is based on a polynomial division. In some such embodiments of the above methods, the sequence of symbols may be found from the remainder determined by the performing a polynomial division on a second sequence. In any embodiments of the first method, the first method may further include writing an evaluated value of a cyclic redundancy check for the data packet into a specific one of the segments of the first sequence in response to the end of the data packet being in the specific one of the segments of the first sequence. In some such embodiments, the modifying may further include receiving a number indicative of the location of the end of the packet in the specific one of the segments of the first sequence. The writing may include determining a location to write the evaluated value based on the received number. One embodiment of a second method involves processing a sequence of disjoint data segments of equal length. The sequence includes a particular data packet. The second method includes masking a portion of one of the data segments. A portion of the particular data packet is in the one of the data segments and is outside of the masked portion. The second method includes modifying a start and/or end of the particular data packet and calculating a cyclic redundancy check for the particular data packet based on the masked segment and the modified particular data packet. In some embodiments of the second method, the second method may include comparing the calculated cyclic redundancy check to zero. In any of the embodiments of the second method, the calculating a cyclic redundancy check may include calculating a check sequence value based at least partially on another cyclic redundancy check transmitted with the data packet. In any of the embodiments of the second method, the second method may include identifying an end-of-packet within the specific one of the data segments. In any of the embodiments of the second method, the second method may include inverting one or more symbols at the start of the data packet. In any of the embodiments of the second method, the second method may include inverting one or more symbols at the end of the data packet. Another embodiment is a system for processing a data packet located in a first sequence of disjoint original segments. Each original segment of the first sequence has the same length. The system includes a masking unit configured to modify one or more symbols in a first of the original segments of the first sequence where a start of the data packet is in the first of the original segments and is after a first symbol therein. The masking unit is configured to modify one or more symbols in a last of the original segments of the first sequence where an end of the data packet is located in the last of the original segments and is before a last symbol therein. The system includes a cyclic redundancy check calculation unit configured to determine a remainder by performing a polynomial division on a second sequence of disjoint consecutive segments. Each segment of the second sequence corresponds to and is derived from one of the original segments. The segments of the second sequence have the length of the original segments. The first of the derived segments of the second sequence is the modified first of the original segments. The last of the derived segments of the second sequence is the modified last of the original segments. In some embodiments of the system, the masking unit may be configured to mask portions of the original segments outside of the data packet such that said portions will not contribute to the remainder determined by the polynomial division when a cyclic redundancy check of the data packet vanishes. In any of the above embodiments of the system, the masking unit may be configured to modify the first of the original segments by modifying symbols at the start of the data packet and to modify the last of the original segments by modifying symbols at the end of the data packet. BRIEF DESCRIPTION OF THE DRAWINGS Advantages of various embodiments may become apparent upon reading the following detailed description and upon reference to the drawings in which: Figure 1A schematically illustrates a digital data communications system that uses a CRC code for the detection of errors, e.g., errors produced by transmitting digital data packets over a physical communication channel; Figure 1B schematically illustrates methods of processing a sequence of digital data symbols to produce a final sequence for a CRC codeword, e.g., in the data communication system as illustrated in Figure 1A; Figure 2 is a flow diagram illustrating a method of decoding a sequence of digital data symbols, e.g., as illustrated in Figure IB, to determine whether the transmission of the sequence caused an error, e.g., a method for use in the receiver illustrated in Figure 1 A; Figure 3 is a flow diagram illustrating a method of encoding a message portion in a sequence of digital data symbols, e.g., as illustrated in Figure IB, to append a CRC check sequence thereto, e.g., a method for use in the transmitter illustrated in Figure 1 A; Figure 4A is a block diagram illustrating one embodiment of an encoder, e.g., for the transmitter illustrated in Figure 1 A, wherein the encoder appends a CRC check sequence to each data packet to be transmitted, e.g., using methods of Figures IB and 3; Figure 4B is a block diagram illustrating one embodiment of a decoder, e.g., for the receiver of Figure 1A, wherein the decoder evaluates whether a received data packet has an error based on a CRC check sequence, e.g., using the methods illustrated in Figures IB and 2; Figure 5 illustrates processing of an example data packet by one specific embodiment of the methods of Figures IB, 2, and 3, e.g., in the encoder illustrated in Figure 4A and/or the decoder illustrated in Figure 4B; Figure 6 is a block diagram illustrating one embodiment of a combined masking unit and partial remainder appending unit that may be used, e.g., in some specific embodiments of the encoder and decoder illustrated in Figures 4A - 4B; Figure 7 is a state diagram illustrating the operation of the combined masking unit and partial remainder appending unit illustrated in Figure 6; and Figure 8 is a block diagram illustrating a specific embodiment of a backwards computation unit that may be used in some embodiments of the encoder illustrated in Figure 4 A. DETAILED DESCRIPTION Various embodiments relate to apparatus, systems, and methods for use in systems that detect transmission errors in digital data packet-based communication systems. Figure 1A illustrates one example of a communication system 10 that transmits information in digital data packets. The communication system 10 includes a transmitter 12, a receiver 14, and a physical communication channel 16 connecting the transmitter 12 to the receiver 14. The transmitter 12 includes an input data processor 18 and an encoder 400A. The data processer 18 receives data for transmission and produces therefrom a stream of data digital packets. Each digital data packet may have, e.g., a header, a message portion, and a reserved portion. The encoder 400A inserts a CRC check sequence in the reserved portions of one or more of the data packets prior to their transmission to the physical communication channel 16. The receiver 14 includes a decoder 400B and an output data processor 20. The decoder 400B checks the received data packets for transmission errors, i.e., based on the CRC check sequences therein, and indicates the data packets found to have an error to the output data processor 20. The output data processor 20 may extract data from the message portions of the data packets that were found to be error-free by the decoder 400B. The receiver 14 may be configured to signal the transmitter 12 to re-transmit data packets found by the decoder 400B to have transmission errors. The physical communication channel 16 supports data communication between the transmitter 12 and the receiver 14. The physical communication channel 16 may include one or more conventional optical fiber transmission lines, wireless transmission media, and/or wire transmission media, or a combination thereof. The communication system 10 may be configured to provide additional packaging of data packets and/or overhead for other methods of error detection and/or correction, e.g., in addition to CRC check sequence-based methods. Figure IB schematically illustrates methods of processing streams of digital data symbols in a communication system that use a binary CRC code to detect data transmission errors, e.g., steps of the method may be performed in the transmitter 12 and/or receiver 14 of Figure 1 A. The method involves operating on a first sequence 32 that includes a total of (a+k+m+b) digital data symbols. The first sequence 32 is formed of consecutive segments of equal length. The first sequence 32 includes a sequence 34 of length (k+m) that forms the message and reserved portions of a data packet-of-interest. The message portion is faithfully represented by a polynomial U(t), and the reserved portion is faithfully represented by a polynomial F(t). In the first sequence, the message portion is preceded by a sequence of "a" data symbols, and the reserved portion is followed by a sequence of "b" data symbols. The method includes masking the first sequence 32 to produce a second sequence 36 that is faithfully represented by a polynomial V(t). In a first embodiment, the masking produces the second sequence 36 by setting to zero those bits of the first sequence 32 that are not located in the message or reserved portions of the data packet. In an alternate second embodiment, the masking produces the second sequence 36 by performing the masking step of the first embodiment and also forming ones complements of the first "m" bits of the message portion and the "m" bits of the reserved portion in the first sequence 32. In Figure IB, the two embodiments are indicated schematically by showing an insertion of "+I(t) " under appropriate bit locations of the data packet, i.e., to illustrate the extra masking operation of the second embodiment. The method includes computing a value of a remainder sequence from the division of the masked second sequence 36 by the sequence that corresponds to the CRC generator polynomial G(t). The remainder is a sequence that is faithfully represented by a polynomial R^v(t). At the receiver, the computed value of the remainder sequence is indicative of the absence or presence of some types of data transmission errors in the received data packet. In embodiments for encoding, the method includes producing a third sequence 38 that will be transmitted from the transmitter to the receiver. The third sequence 38 is formed by replacing the reserved portion 40 of the data packet by a CRC check sequence (in the above-described first embodiment) or a ones complement of such a CRC check sequence (in the above-described first embodiment). Herein, the CRC check sequence or ones complement thereof are represented by a polynomial "F(f) + £>(/)" where the polynomial F{t) faithfully represents the original sequence in the reserved portion in the first sequence 32 and D(t) represents the adjustment sequence that causes 34 to become a codeword. Below, steps illustrated in Figure IB and notations therein are described in more detail. Herein, a data packet contains disjoint message and reserved portions, wherein both of said portions are formed by finite sequences of digital symbols in a finite symbol alphabet A-The alphabets may be a finite Galois field, e.g., the mod 2 integers or strings of 1 's and 0's of a fixed preselected length. The message portion is a stream of A: digital symbols Uk-i Uk-2 ••• w; «o, which is faithfully represented as an order-A polynomial U{t) of the form: In the polynomial U(t), the power of"?" determines the temporal position of the corresponding digital symbol in the first stream. The reserved portion may be located, e.g., immediately after the message portion. Prior to encoding, the reserved portion holds a stream of m digital symbols fm-ifm-2 —fifo, which is faithfully represented by an order-m polynomial F{t) of the form: Encoding rewrites the reserved portion of the data packet with a CRC check sequence portion of fixed length "m" or a ones complement thereof. The CRC check sequence has the form cm.\ cm.2 ... cj Co e J?™, which is faithfully represented by a CRC check sequence polynomial of the form: In first embodiments, e.g., as described with respect to Figure IB, the corresponding message and CRC check sequence portions form a codeword of symbol length n = k + m, which is faithfully represented by a polynomial, X(f), which satisfies: In the polynomial X(t), higher-order "/" terms correspond to the digital data symbols of the message portion of the digital data packet itself and lower-order "/" terms correspond to the digital symbols of the CRC check sequence portion of the digital data packet. Herein, a codeword refers to a polynomial in "f" that is exactly divisible by a preselected and fixed CRC generator polynomial in "/", i.e., the polynomial is divisible without a non-zero remainder. The preselected and fixed CRC generator polynomial G{i) may be written as: The special CRC generator polynomial of Equation (1) is known as the CRC-32 polynomial and is specified by several standards, e.g., the IEEE 802.3 Ethernet standard. Various embodiments of methods and apparatus described herein, may be configured to use the CRC-32 polynomial or another polynomial as the CRC generator polynomial. In such first embodiments, the CRC check sequence polynomial C(J) is chosen such that U{t)-f + C(t) is divisible by the CRC generator polynomial G{f), i.e., such that U(t)-tm+ C(t) is a codeword. In particular, the remainder R(t) of division of U(t)-f" by the CRC generator polynomial G{f) is defined by: Here, the remainder polynomial R(i) corresponds to a digital symbol sequence rm.i rm.2 ... r\ ro . Thus, the CRC check sequence polynomial may satisfy C(t) = -R(t) where the minus of any coefficient is the additive inverse of the coefficient in the algebra^. In a binary CRC code, -R(t) = R(t), because the algebra Jl of a binary CRC code is the integers modulo 2 and 1+1=0 for the integers modulo 2. Thus, the CRC check sequence polynomial is R(f) for this algebra. In a data communications system using such an implementation of a CRC code, the transmitter, e.g., the transmitter illustrated in Figure 1 A, sends a stream of digital data symbols. In the stream, each transmitted digital data packet includes a separate message portion and a CRC check sequence portion that together correspond to a codeword X(t). Each digital data packet may also include a separate packet header and/or packet container, which are not part of the message and CRC check sequence portions of the data packet. In response to the transmission of the data packet corresponding to the codeword^?), the receiver receives a sequence of digital data symbols that corresponds to a polynomial Y(f), where Y(t) =X(t) + E(f). Here, E{f) is a polynomial faithfully representing the locations and values of the errors in the received data packet. To determine whether a transmission error has occurred, the receiver, e.g., the receiver 14 as illustrated in Figure 1 A, evaluates a remainder of a polynomial division of Y(t) by the CRC generator polynomial G(t). In the absence of any transmission errors, the remainder of Y(t) divided by the CRC generator polynomial G(f) is a polynomial with zero coefficients, i.e., Y(t) is a codeword. In the presence of one or more transmission errors, the remainder of this division is likely to be non-zero, i.e., an error is detectable unless E(f) is itself a codeword. For example, for special generator polynomials of order m, any error sequence that is a cyclic shift of a polynomial of degree less than m produces a polynomial Eft) that is not codeword. Thus, in a received data packet, such errors are detectable via a determination of whether the corresponding polynomial Y(t) is a codeword. In second embodiments, e.g., the second embodiment described with respect to Figure IB, encoding includes initializing the "TW" memory elements that will hold the remainder R(f) with an all-ones sequence and effectively evaluating a remainder R(f) of the polynomial division of the polynomial U(t)-f + I(t)-f by the CRC generator polynomial G(t) where I(t) = f'1 +f'2 + ... + t + 1. Thus, the polynomial R(f) satisfies: In these second embodiments, the transmitted portions of a third sequence for the message and reserved portions of the data packet are faithfully represented by a codeword X(Y) that satisfies X(f) = U(t)-f + C(t) where C(t) = R(t) + 1(f) = F(t) + D(f). Herein, for these second embodiments of CRC coding, a data packet is faithfully represented by a polynomial that is a codeword if dividing the polynomial by the CRC generator polynomial G(t) produces an all-ones polynomial of order "m" where the reserved portion of the data packet has length "AW". Thus, the receiver may initialize memory elements specifically for the CRC check sequence with an all-ones sequence and then determine whether the remainder of a polynomial division of the received sequence corresponding to Y(f), i.e., X(t) + E{t), by the CRC generator polynomial G(f) produces an all-zeros sequence to decide whether the data packet has a transmission error. The medium access control (MAC) layer in the IEEE 802.3 standard uses this alternate procedure with the standard CRC-32 generator polynomial G(f) of Equation (1). Figures 2 and 3 illustrate methods 200, 300 for processing data packets that are based on a cyclic redundancy code (CRC) over the binary algebra defined by modulo addition on 0 and 1. The encoding method 300 involves preparing each data packet for transmission by evaluating a CRC check sequence for a message portion of the data packet and appending a CRC check sequence or a ones complement thereof to the message portion, e.g., in the encoder 400A illustrated in Figure 1 A. The appending step forms a sequence that corresponds to a CRC codeword. The decoding method 200 involves determining whether a received data packet has a CRC-detectable transmission error by determining whether the data packet corresponds to a CRC codeword, e.g., in the decoder 400B illustrated in Figure 1 A. The definitions of "codeword" have already been described with respect to the first and second embodiments of Figure IB. At steps 210 and 310, the methods 200, 300 include, in a segment-by-segment manner, receiving segments of a first sequence that has a digital data packet therein, e.g., the receiving may be performed in the encoder 400 A or the decoder 400B as illustrated in Figures 1 A. The first sequence is a sequence of "q" segments, wherein each segment has the same length "s". Each first sequence includes a message portion of the data packet, whose sequence of bits corresponds to a polynomial U(f), and a reserved portion of the data packet, whose sequence of "m" bits corresponds to a polynomial F(t), i.e., in these methods 200, 300 of Figures 2-3. The reserved portion may immediately follow the message portion of the data packet. The message and reserved portions are typically located in the message portion of the data packet, e.g., after the packet header. In the first sequence, "a" bits precede the sequence corresponding to U(t) f + F(t), and "b" bits follow the sequence corresponding to U{t) f + F(t). Thus, q-s = n + a + b where "q" is the number of segments in the first sequence, 'V is the number if bits in a segment, and "«" is the number of bits in the sequence corresponding to U(t) f + F(f). Here, the values of the integers "a", "b", and "«" may vary from data packet to data packet due to the different possible locations of a data packet in the first sequence and different possible lengths of a data packet. In the examples described below, the length of each segment is short enough to ensure that message portions of no more than two consecutive data packets are located in the same segment. In some other embodiments, the segments may be longer so that a part of the message portion of one data packet, message portion(s) of zero, one or more subsequent data packets, and part of the message portion of another data packet may be in one segment. At steps 220 and 320, the methods 200, 300 include sequentially masking the "q" segments of the first sequence as the segments are received, e.g., the masking may be performed in the encoder 400A or the decoder 400B as illustrated in Figures 1 A. In a segment-by-segment manner, the masking produces a second sequence of segments in which i) the "a" bits preceding the sequence corresponding to U{i) f + F(t) are zeros, and ii) the "6" bits following the sequence corresponding to U(f) f + F(t) are zeros. In some specific embodiments, e.g., the above-described second embodiments described with respect to Figure IB, the masking steps 220 and 330 also involve: i) inverting the leading "m" bits of the sequence corresponding to U{t) f + F(t) and/or ii) inverting the final "AW" bits of the sequence corresponding to U(t) f + F(f). These specific embodiments perform this option inverting (i.e., ones complementing) of the initial "w" bits and final "m" bits of the concatenation of the message and reserved portions of the data packet. In such embodiments, the second sequence of segments is faithfully represented by a polynomial V(t) of the form: At steps 230 and 330, the methods 200, 300 involve processing the second sequence, which corresponds to the polynomial V(t), in a segment-by-segment manner that corresponds to recursively dividing the polynomial V(t) by the CRC generator polynomial G{t). The steps 230 and 330 involve computing a remainder sequence corresponding to a polynomial Fy\i) that is the remainder of a division of the polynomial V(t) by the CRC generator polynomial G(f). Thus, the processing steps 230, 330 effectively perform a division of V(t) by the CRC generator polynomial G(t) rather than performing a division of the message portion U(t) of the data packet by the CRC generator polynomial G(t). At step 240, the method 200 determines whether the portion of the first sequence corresponding to the message and reserved portions of the data packet form a CRC codeword based on the remainder computed at the step 230. If this portion of the first sequence is determined to be a codeword, the method 200 includes signaling, at 250, that the data packet is transmission error-free. If this portion of the first sequence is determined to not be a codeword, the method 200 includes signaling, at 260, that the data packet has a transmission error. At step 340, the method 300 involves adjusting the reserved portion of the data packet such that the message and reserved portions of the data packet form a sequence corresponding to a CRC codeword. The step 340 may involve determining a sequence corresponding to a check sequence difference polynomial D{i) and creating a final sequence for the message and reserved portions of the data packet. The final sequence is faithfully represented by the polynomial U(t)-f + D(t) + F(t). In the above-described first embodiments, from the form of V(t), it follows that: If the sequence for the computed remainder polynomial R^b)(t) is an all-zeros sequence of at least length m, then F{t) = C(i), and the step 340 determines that £>(/) = 0. If instead, the computed remainder polynomial Ryb)(t) is a non-zero polynomial whose length is equal to or less than m, then C(f) = F(t) + D(t) where the non-zero check sequence difference polynomial D{f) satisfies: Then, the step 340 may effectively involve solving Equation (6) via a backwards computation to obtain the symbol sequence for check sequence difference polynomial D(t) from the computed sequence for the computed remainder polynomial Rw(t). The step 340 may involve backwards computing the polynomial R{0)(t) from the computed remainder polynomial i?(A)(/) by recursively solving another equation relating remainders R{l\t) for different numbers "6" of trailing zeros in the sequence for the polynomial V(t). In particular, the equations relating remainders can be rewritten in a reverse-ordered form from the reverse-ordered generator polynomial. For example, R^~S)(t) can be obtained from a remainder involving Ry\t) by solving the equation: That is, coefficients of (z-<5)-th remainder polynomial Ry~S)(t) are equal to a remainder obtained from dividing the z'-th reverse-ordered remainder polynomial Rv0(r]) tm+s by the reversed-order fixed polynomial G(t~l) tm, i.e., G{t~l)-tm = g0tm + g^""1 + + gmJ + gm. For this reason, the above described recursive process can also be performed with reverse-ordered forms of remainders to obtain D(t) = R{0\t) from the computed remainder polynomial R(b)(t). For example, one method to perform this computation for arbitrary a range of values of "6" in a certain range is described in more detail below in connection with Figure 8. In the above-described second embodiments, the check sequence difference polynomial D(t) is the difference between the polynomial R(t) + I(t) and the polynomial F(t), which corresponded to the reserved portion of the data packet in the first sequence. The polynomial R{f) + I(t) corresponds to the ones complement of the remainder of a division of the polynomial U(t) + I(t)-t^'m) for the message portion of the data packet by the CRC generator polynomial G(t). In this embodiment, the sequence for the polynomial R(f) could also be found by backwards calculations from the sequence for the computed remainder polynomial R(b)(t) based on modified versions of Equations 6-8, which account for the inversions in the polynomial V(t) as shown in above Equation (4) for the second embodiments. A person of ordinary skill in the art would be able to easily determine said modified equations based on the above descriptions of Equations 4-8. At step 340, the method 300 also sequentially transmits to a destination receiver a final sequence in which the data packet has the original message portion and in which the message and reserved portions form a CRC codeword faithfully represented by the polynomial U{t)-f + D(t) + F(i). In the below-described embodiments, a "word" is typically "one byte". Figures 4A and 4B illustrate an encoder 400A and a decoder 400B, respectively. The encoder 400A may, e.g., perform the encoding method 300 of Figure 3, and the decoder 400B may, e.g., perform the decoding method 200 of Figure 2. The encoder 400A and decoder 400B are, e.g., conventional digital hardware devices, e.g., formed of circuits including gates, flip-flops, registers, adders, and/or multipliers. The encoder 400A and decoder 400B illustrated in Figures 4A - 4B may be, e.g., the respective encoder 400A and decoder 400B illustrated in Figure 1 A. The encoder 400A and/or decoder 400B may be located in a network interface card (NIC) or a transport network element (TNE), e.g., an Ethernet NIC or TNE, of a transceiver for wired, wireless, or optical packet-based communications. As shown in Figures 4A and 4B, the encoder 400A and decoder 400B include a set of digital data processing units. The set of digital processing units includes a segmenting unit 410; a masking unit 420; a partial remainder appending unit 425; segment division units 430,435; a remainder processing unit 440; and one or more digital buffers 460,462, 464,466. The encoder also has a backwards computation unit 470 and a check sequence adjustment unit 480. The decoder 400B also has a check sequence verification unit 490. Various ones of the digital processing units process the received stream of data symbols in a substantially temporally sequential segment-by-segment manner in which each segment has the same length. The segmenting unit 410 receives a stream of digital data symbols and consecutively transmits each consecutive equal-length segment to the masking unit 420 and information on each segment to the masking unit 420 and the partial remainder appending unit 425. The segmenting unit 410 receives the stream at input 401 and outputs segments of said stream at output 412. For each data packet, the segmenting unit 410 outputs a sequence of "q" consecutive segments where "q" may vary from data packet-to-data packet. But, each segment is S w bytes long, i.e., s bits where s = wS and w is the number of bits in a word. In the description below, the segments are assumed to be byte-aligned. The results can be easily extended to process segments that are not word-aligned. For each segment, the segmenting unit 410 transmits information corresponding to the segment to output port 414. The information identifies and locates any data packet start and/or data packet end located in the corresponding segment. If a segment has a data packet start, the segmenting unit 410 outputs a start-of-packet (SOP) signal of the value 1 and a start-of-packet index (SPI) that identifies the position of the data packet start in the segment. If a segment does not have a data packet start, the segmenting unit 410 outputs a SOP signal of the value 0. If a segment has a data packet end, the segmenting unit 410 outputs an end-of-packet (EOP) signal of the value 1 and an end-of-packet index (EPI) that identifies the position of the data packet end in the segment. If the segment does not have a data packet end, the segmenting unit 410 outputs an EOP signal of the value 0. The segmenting unit 410 may identify and locate a data packet start and/or a data packet end by reading a packet length identifier (PLI) in the packet header of the data packet. Below, consecutive words of a segment are indexed in order of transmission by numerals (S - 1) to 0 where higher index corresponds to earlier transmitted words. The SPI and EPI signals may be represented by a vector of length "/' of binary signals (i.e., 27"1

Documents

Application Documents

# Name Date
1 4189-CHENP-2012 POWER OF ATTORNEY 11-05-2012.pdf 2012-05-11
1 4189-CHENP-2012-AbandonedLetter.pdf 2018-08-28
2 4189-CHENP-2012-FER.pdf 2018-01-22
2 4189-CHENP-2012 PCT OTHERS 11-05-2012...pdf 2012-05-11
3 4189-CHENP-2012 CORRESPONDENCE OTHERS 21-02-2014.pdf 2014-02-21
3 4189-CHENP-2012 FORM-5 11-05-2012.pdf 2012-05-11
4 4189-CHENP-2012 FORM-3 21-02-2014.pdf 2014-02-21
4 4189-CHENP-2012 FORM-3 11-05-2012.pdf 2012-05-11
5 4189-CHENP-2012 CORRESPONDENCE OTHERS 07-10-2013.pdf 2013-10-07
5 4189-CHENP-2012 FORM-2 11-05-2012.pdf 2012-05-11
6 4189-CHENP-2012 FORM-3 07-10-2013.pdf 2013-10-07
6 4189-CHENP-2012 FORM-18 11-05-2012.pdf 2012-05-11
7 4189-CHENP-2012 FORM-1 11-05-2012.pdf 2012-05-11
7 4189-CHENP-2012 FORM-3 15-11-2012.pdf 2012-11-15
8 4189-CHENP-2012 DRAWINGS 11-05-2012.pdf 2012-05-11
8 4189-CHENP-2012 CORRESPONDENCE OTHERS 15-11-2012.pdf 2012-11-15
9 4189-CHENP-2012 DESCRIPTION (COMPLETE) 11-05-2012...pdf 2012-05-11
9 4189-CHENP-2012 FORM-3 26-09-2012.pdf 2012-09-26
10 4189-CHENP-2012 CORRESPONDENCE OTHERS 26-09-2012.pdf 2012-09-26
10 4189-CHENP-2012 CORRESPONDENCE OTHERS 11-05-2012.pdf 2012-05-11
11 4189-CHENP-2012 CLAIMS 11-05-2012.pdf 2012-05-11
11 4189-CHENP-2012 CORRESPONDENCE OTHERS 11-06-2012.pdf 2012-06-11
12 4189-CHENP-2012 ABSTRACT 11-05-2012.pdf 2012-05-11
13 4189-CHENP-2012 CLAIMS 11-05-2012.pdf 2012-05-11
13 4189-CHENP-2012 CORRESPONDENCE OTHERS 11-06-2012.pdf 2012-06-11
14 4189-CHENP-2012 CORRESPONDENCE OTHERS 26-09-2012.pdf 2012-09-26
14 4189-CHENP-2012 CORRESPONDENCE OTHERS 11-05-2012.pdf 2012-05-11
15 4189-CHENP-2012 FORM-3 26-09-2012.pdf 2012-09-26
15 4189-CHENP-2012 DESCRIPTION (COMPLETE) 11-05-2012...pdf 2012-05-11
16 4189-CHENP-2012 CORRESPONDENCE OTHERS 15-11-2012.pdf 2012-11-15
16 4189-CHENP-2012 DRAWINGS 11-05-2012.pdf 2012-05-11
17 4189-CHENP-2012 FORM-3 15-11-2012.pdf 2012-11-15
17 4189-CHENP-2012 FORM-1 11-05-2012.pdf 2012-05-11
18 4189-CHENP-2012 FORM-18 11-05-2012.pdf 2012-05-11
18 4189-CHENP-2012 FORM-3 07-10-2013.pdf 2013-10-07
19 4189-CHENP-2012 FORM-2 11-05-2012.pdf 2012-05-11
19 4189-CHENP-2012 CORRESPONDENCE OTHERS 07-10-2013.pdf 2013-10-07
20 4189-CHENP-2012 FORM-3 21-02-2014.pdf 2014-02-21
20 4189-CHENP-2012 FORM-3 11-05-2012.pdf 2012-05-11
21 4189-CHENP-2012 CORRESPONDENCE OTHERS 21-02-2014.pdf 2014-02-21
21 4189-CHENP-2012 FORM-5 11-05-2012.pdf 2012-05-11
22 4189-CHENP-2012-FER.pdf 2018-01-22
22 4189-CHENP-2012 PCT OTHERS 11-05-2012...pdf 2012-05-11
23 4189-CHENP-2012-AbandonedLetter.pdf 2018-08-28
23 4189-CHENP-2012 POWER OF ATTORNEY 11-05-2012.pdf 2012-05-11

Search Strategy

1 4189-chenp-2012_22-09-2017.pdf