Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-04-17
2003-07-29
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S785000, C370S474000
Reexamination Certificate
active
06601208
ABSTRACT:
BACKGROUND
1. Field of Invention
The field of this patent is in the area of forward error correction and its applications.
2. Description of Related Art
All information transmission protocols are block structured.
Block structured block codes are standardized for error detection and re-transmission.
Block codes, particular short code lengths, are scarce and less powerful.
convolutional codes are known to produce a large number of optimal block codes
All Internet transmission relies on a set of transmission protocols.
All Internet transmission protocols rely on error detection and re-transmission, or error detection without re-transmission
The Internet Transmission Protocols
For transmission, the key mechanism of the Internet is the following set major protocols:
TCP (Transmission Control Protocol),
(Internet Protocol),
ICMP (Internet Control Message Protocol),
IGMP (Internet Group Management Protocol),
PPP (Point to Point Protocol)
FTP, TFTP (Trivial File Transfer Protocol),
UDP (User Datagram Protocol),
IMP (Internet Multicast Protocol),
Under ICMP, there exists transmission protocols for address, timestamp request and reply, router solicitation, router advertisement, Echo request and reply, timing exceeded messages, redirected messages, and unreachable messages. Each transmission protocol has its unique format and structure, and they have been specified by the IETF as standards. Each of these protocols contains the provision of either Checksum, or ARU, or CRC for error detection and/or re-transmission.
Error Detection and/or Re-transmission
For error protection, telecommunication industry depends on error detection and re-transmission. All present and planned Internet transmission schemes rely on either error detection or re-transmission, or no error detection but waiting for delayed non-response time. The error detection and re-transmission techniques have been referred to as automatic repeat request (ARQ). The delayed response and re-transmission schemes have been referred to as the Windowed method. The Window size, specified by the IETF (Internet Engineering Task Force) and practiced by all the ISPs (Internet Service Providers), is related to the amount of delay time allowed.
All ARQ use error codes without forward correction capability. These ARQ codes are selected, internationally standardized, and called CRC (Cyclic Redundancy Checks). The generator polynomials of the CRC codes are:
g
(
CRC
-
4
)
=
1
+
x
+
x
2
+
x
3
+
x
4
g
(
CRC
-
7
)
=
1
+
x
4
+
x
6
+
x
7
g
(
CRC
-
8
)
=
(
1
+
x
)
(
1
+
x
+
x
2
)
(
1
+
x
2
+
x
3
+
x
4
+
x
5
)
g
(
CRC
-
12
)
=
1
+
x
+
x
2
+
x
3
+
x
11
+
x
12
g
(
CRC
-
16
a
)
=
1
+
x
2
+
x
15
+
x
16
g
(
CRC
-
16
b
)
=
1
+
x
5
+
x
12
+
x
16
g
(
CRC
-
16
c
)
=
1
+
x
+
x
2
+
x
4
+
x
7
+
x
13
+
x
15
+
x
16
g
(
CRC
-
24
)
=
1
+
x
8
+
x
12
+
x
14
+
x
23
+
x
24
g
(
CRC
-
32
)
=
1
+
x
+
x
2
+
x
4
+
x
5
+
x
7
+
x
8
+
x
10
+
x
11
+
x
12
+
x
16
+
x
23
(
1
)
The CRC-16a has been standardized by ANSI. The CRC-16b has been standardized by the ITU-T and widely used worldwide. The CRC-16c has been standardized for SDLC. For CRC-32 there exist two more versions depending on the applications. For the Internet transmission, some protocols have specified one or more of the above CRCs. But most Internet Transmission Protocols rely on the structure of Checksums for error protection as to be described next.
The Checksum Computations
Based on ordinary arithmetic computations in computers the technique of Checksum was developed based on arithmetic coding. In this case, the numbers are represented by a set of polynomials in a radix system. For every such number, there is a unique binary representation in terms of the powers of the radix=2 and coefficients +1, −1, or 0. To encode a number n, multiply n by a factor of the radix r, then add a value b. That is, the coded form is c=nr+b. To decode, the decoder first subtract b from c, then divide by r. If the division produces a nonzero remainder, an error is detected. The condition here requires that n is relatively prime to r.
Presently, the Internet uses 16-bit bytes in its Checksum portion of all the transmission protocol formation. The Checksum function is the one's complement sum. That is, additions are performed with arithmetic carry on the bytes. It is the one's complement of this sum that is stored in all the protocols, which contains Checksums. For Checksums the radix base r is chosen to be 2
16
. This way, every 16-bit byte is considered as a digit of a number, and this number is the message.
The implementation of the Internet Checksum is the result of conversion of the division computation to addition. This is based on the following identity valid for r=2
16
−1 and any digit D in radix r:
D*r
j
=D
mod(
r−
1) (2)
In the statement, any digit D in radix r multiply any power of the radix will have a remainder D when divided by the radix minus one. Thus, the remainder of a number divided by the radix minus one can be obtained by adding the digits of the number. Thus the required division process becomes addition operation and the decoding in Checksum becomes summing all the 16-bit words with carries. As a result, errors can be detected after the summation procedure.
The Checksum operation is described as:
Two adjacent 8-bit symbols are pair-wise checksum to form 16-bit integers.
The 1's complement sum of these 16-bit integers is then formed.
The 16-bit 1's complement sum is computed over the set of message symbols.
The 1's complement of this sum is the 16-bit Checksum for encoding.
To perform error detection, the 1's complement sum is computed over the same set of message symbols.
If the computed result is all 1's, (−0 in 1's complement arithmetic) check is completed.
Limitations and Problems
The severity of limitation and problem depends on the application, client's demand, server's availability, and network condition, at that time. In most cases, limitations and problems are separately treated and improvements are separately sought.
Network and Throughput Problems
The Internet network operators are using load balancing algorithms, scheduling techniques, renaming network elements, rotating servers, and user message behavior in order to optimize the network utilization. These algorithms and procedures require constant monitoring and updating. As a consequence, the operations not only become complicated and costly, but also decrease the network throughput.
Bandwidth and Congestion Problems
As the Internet traffic increases, congestion is expected, and bandwidth has been recognized as scarce commodity. In addition to loading balancing and message sensing methods, advance service such as Differential Service technique and its variation have been proposed in order to conserve bandwidth. But these techniques cause delay and create uncertainty and undesirability from a client's viewpoint.
Efficiency and Reliability Problems
Transmission protocols are the backbones of the Internet. There are four basic layers in protocol internetworking architecture: the Application Layer, the Transport Layer, the Inter-network Layer, and the Network Interface Layer. The last one is also called data link layer, which provides interface to the networks such as ATM, FDDI. The IP is the heart of the Inter-network Layer, which does not provide any measure of link reliability. The only error protection mechanism in the IP is a very simple error detection scheme for the protection of the Header.
At the receiving end, if an error is detected in the IP Header, the entire Header and the corresponding message are discarded. There is no provision for re-transmission request. Even in the absence of heavy user traffic, different time delay has been experience
Creighton Wray James
Narasimhan Meera P.
Tu Christine T.
LandOfFree
Forward error correction techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Forward error correction techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forward error correction techniques will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3103305