Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2002-08-30
2004-01-06
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S785000
Reexamination Certificate
active
06675346
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a code transmission scheme to be used for the purpose of realizing reliable end-to-end communications between networks, especially computers.
2. Description of the Background Art
The computer communication conventionally adopts a scheme in which data are sequentially transferred between small sized networks called subnets via devices such as bridges and routers. Here, a data unit for transfer is called an IP (Internet Protocol) packet.
The IP packet transfer has been realized on the best effort basis historically, where it is assumed that data can be discarded or lost at network devices such as switches and routers provided within the network. Then, when an IP packet transmitted from a transmitting side fails to reach a receiving side, in general, either an end-to-end re-transmission has been carried out (by TCP (Transmission Control Protocol), for example), or no action has been taken (by UDP (User Datagram Protocol), for example) even if this communication fails.
Also, conventionally, communications using computers have been predominantly of point-to-point type. However, recently, there is an increasing need for communications using multicast. Conventionally, in the case of realizing multicast, it has been common to adopt a scheme in which UDP and the like is used as the upper level protocol and no request for high quality is allowed. The reason for this is that, if the end-to-end re-transmission control is carried out by utilizing the multicast, a number of ACK (Acknowledgement)/NACK (Negative Acknowledgement) signals for indicating whether the receiving has been successful or not from the receiving side increases in proportion to a number of receiving terminals, so that the processing load at a transmitting terminal can be increased.
In view of such a background, there have been propositions for a scheme using end-to-end error correction as a scheme for realizing both a multicast system and reliable communications.
As a first example, a communication scheme that secures the end-to-end reliability by adding error correction cells using Reed-Solomon (RS) codes to a plurality of ATM cells has been disclosed in Japanese Patent Application Laid Open No. 8-186570 (1996). According to this scheme, the usual Reed-Solomon code is separated into the information section used as ATM cells for data and the redundant section used as ATM cells for codes, so that when m cells for data and one cell for codes are provided, it is possible to recover discarded cells up to one cell among (m+1) cells using the error correction. By such an application of the error correcting codes, it is possible to realize high quality end-to-end communications.
However, this scheme is associated with the following problem. In general, it is preferable to be able to set the level of redundancy individually by a communication network. However, because the usual code words are used currently, it is necessary to carry out different coding calculating processing when the number of redundant cells to be attached is changed.
More specifically, the RS code has the redundant section which is a residue obtained by dividing the information section by a polynomial called G(X). For instance, in the case of using one cell redundancy, G(X) can be expressed as:
G
(
X
)=
X−&agr;
b
(1)
where &agr; is a root of a primitive polynomial used as a base of this code production, and b is an integer whose value is predetermined between the transmitting side and the receiving side. In other words, G(X) must be shared at the transmitting side and the receiving side. However, in the cases of two cells redundancy and three cells redundancy, G(X) can be expressed respectively as:
G
(
X
)=(
X−&agr;
b
)(
X−&agr;
(b+1)
) (2)
G
(
X
)=(
X−&agr;
b
)(
X−&agr;
(b+1)
)(
X−&agr;
(b+2)
) (3)
In these cases, the respective polynomials have different degrees so that it is necessary to carry out a division calculation separately for each of them. This implies in terms of the hardware implementation that there is a need to provide completely separate calculation circuit for each of them so that it can cause an increase in the circuit size. Also, in terms of the software program, this implies that a separate program must be produced for each of them, so that it can cause an increase in the amount of software programs.
Next, as a second example of a proposition for a scheme using end-to-end error correction, a scheme which is conceived as a technique for combining the error correction and the re-transmission will be described. This scheme is considered particularly effective in the case of multicast.
First, a sender sends m information packets and l redundant packets that are associated with these information packets to a receiver, where l is a 0 or a positive integer. When the receiver detects that l or less packets among (m+l) packets fails to arrive, the correction using the redundant packets is carried out. However, when discarding of l′ packets (l′>l) occurs in the middle, the receiver requests the re-transmission of (l′−l) packets to the sender. In response, the sender newly produces (l′−l) redundant packets and sends them to the receiver. As a result, the receiver obtains l′ redundant packets so that it becomes possible to recover the original information packets by carrying out the error correction with respect to discarding of l′ packets.
In this scheme, the sender is initially capable of producing l redundant packets using the method as explained in the first example, but there is a problem as to how (l′−l) redundant packets are to be produced subsequently. For instance, suppose that the transmission using two packets redundancy with l=2 is carried out initially as in the first example, using G(X) given by:
G
(
X
)=(
X−&agr;
b
)(
X−&agr;
(b+1)
) (4)
and suppose that four packets fail to arrive at the receiving side due to discarding. In such a case, the re-transmission request for remaining two packets will be issued from the receiving side to the transmitting side. In response, the transmitting side is required to produce the redundant packets using, for example, a polynomial given by:
G′
(
X
)=(
X−&agr;
(b+2)
)(
X−&agr;
(b+3)
) (5)
At this point, it is meaningless to use the equation (4) because that would result in the transmission of the same redundant packets, so that it is necessary to use the polynomial like that of the equation (5) which uses different powers of &agr;. Consequently, there is a need to newly produce G′(X) according to the number of re-transmission packets requested from the receiving side, and therefore there are problems of an increase in the circuit size and an increase in the amount of software programs similarly as in the first example.
Thus, conventionally, the re-transmission control using a protocol such as TCP has been carried out for data that requires the reliability, but a scheme using the error correction for the purpose of dealing with multicast has appeared. However, in the conventional scheme that transmits the redundant section of the usual error correcting codes as it is, there is a problem that the number of redundant packets cannot be changed flexibly. In addition, even in the case of combining that with the re-transmission control, there is also a problem that the redundant packets cannot be provided flexibly at a time of re-transmission.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a code transmission scheme for a communication system using error correcting codes, which is capable of reducing a circuit size and an amount of software programs without affecting the error correction performance.
It is another object of the present invention to provide a flexible error correction scheme according to a state of c
De'cady Albert
Foley & Lardner
Kabushiki Kaisha Toshiba
Torres Joseph D.
LandOfFree
Code transmission scheme for communication system using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Code transmission scheme for communication system using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Code transmission scheme for communication system using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3250744