Efficient memory addressing for convolutional interleaving

Details Efficient memory addressing for convolutional interleaving Efficient memory addressing for convolutional interleaving

2000-01-10

2002-07-16

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Data formatting to improve error detection correction...

Reexamination Certificate

active

06421796

ABSTRACT:

CROSS REFERENCE TO RELATED APPLICATIONS
Not applicable.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable.
BACKGROUND OF THE INVENTION
This invention is in the field of data communications, and is more specifically directed to error protection in data communications.
Recent advances in the electronics field have now made high-speed digital data communications prevalent in many types of applications and uses. Digital communication techniques are now used for communication of audio signals for telephony, with video telephony now becoming available in some locations.
The quality of communications carried out in these ways depends upon the accuracy with which the received signals match the transmitted signals. Some types of communications, such as audio communications, can withstand bit loss to a relatively large degree. However, the communication of digital data, especially of executable programs, requires exact fidelity in order to be at all useful. Accordingly, various techniques for the detection and correction of errors in communicated digital bit streams have been developed. Indeed, error correction techniques have effectively enabled digital communications to be carried out over available communication facilities, such as existing telephone lines, despite the error rates inherent in high-frequency communication over these facilities.
Error correction may also be used in applications other than the communication of data and other signals over networks. For example, the retrieval of stored data by a computer from its own magnetic storage devices also typically utilizes error correction techniques to ensure exact fidelity of the retrieved data; such fidelity is, of course, essential in the reliable operation of the computer system from executable program code stored in its mass storage devices. Digital entertainment equipment, such as compact disc players, digital audio tape recorders and players, and the like also now typically utilize error correction techniques to provide high fidelity output.
An important class of error detection and error correction techniques is referred to as Reed-Solomon coding, and was originally described in Reed and Solomon, “Polynomial Codes over Certain Finite Fields”,
J. Soc. for Industrial and Applied Mathematics
, Vol. 8 (SIAM, 1960), pp. 300-304. Reed-Solomon coding uses finite-field arithmetic, such as Galois field arithmetic, to map blocks of a communication into larger blocks. In effect, each coded block corresponds to an over-specified polynomial based upon the input block. Considering a message as made up of k m-bit elements, a polynomial of degree n−1 may be determined as having n coefficients; with n greater than k (i.e., the polynomial is overspecified), not all of the n coefficients need be valid in order to fully and accurately recover the message. According to Reed-Solomon coding, the number t of errors that may be corrected is determined by the relationship between n and k, according to
t
≤
n
-
k
2
.
Reed-Solomon encoding is used to generate the encoded message in such a manner that, upon decoding of the received encoded message, the number and location of any errors in the received message may be determined.
Reed-Solomon decoding is especially beneficial in the detection and correction of random errors in a communicated bitstream. However, the limitation in the number of errors (i.e., the specified value t) that may be corrected by Reed-Solomon techniques precludes the correction of errors of a type referred to in the art as “burst errors”. Burst errors refer to a contiguous error block in the communication channel, generally caused by effects in the communications facility, such as between the transmitting and receiving modems in a telephone communication implementation. Reed-Solomon techniques are generally unable to correct burst errors, because the number of errors in a given vector having a burst error is much greater than the Reed-Solomon correction limit t.
Convolutional interleaving is a conventional technique used to overcome this limitation of Reed-Solomon coding. In a general sense, convolutional interleaving operates by scrambling the time sequence of the transmitted bitstream from that of the conventional first-in-first-out sequence. At the receiving end, the received bitstream is then descrambled, or resequenced, to recover the transmitted message or data. Because of the scrambled sequence of the transmitted data, a burst error occurring within the scrambled bitstream over the communications facility will be dispersed over time. This reduces the density of the burst error in the actual transmitted message, permitting correction of the errors by subsequent Reed-Solomon decoding.
In general, convolutional interleaving introduces varying delay between adjacent codewords in a sequence, such that the temporal sequence of codewords, as transmitted, differs from the message sequence; an inversely varying delay is then introduced between received adjacent codewords, to restore the sequence. Attention is directed, in this regard, to
FIG. 1
which illustrates the operation of conventional convolutional interleaving.
As shown in
FIG. 1
, demultiplexer
2
receives an input datastream on lines IN. This input datastream consists of a time series of symbols, each symbol containing M bits, according to the desired protocol. For example, conventional (
204
,
188
,
8
) Reed-Solomon coded transmissions generally operates according to eight-bit, or one byte, symbols (M=8). Demultiplexer
2
sequentially forwards symbols to N paths
5
I
0
through
5
I
N−1
, of varying delay length. In this regard, demultiplexer
2
may be considered to include a buffering function, such that a vector of N symbols (or a multiple of N) is simultaneously applied to paths
5
I. As described in Forney, “Burst-Correcting Codes for the Classic Bursty Channel”,
IEEE Trans. on Communications Technology, Vol. COM-
19, No. 5 (October 1971), use of convolutional interleaving in combination with downstream Reed-Solomon decoding is optimized using a number of paths that is equal to the size N of the Reed-Solomon block length. The symbol or symbols in this vector that are applied to path
5
I
0
immediately precede, in the time sequence on lines IN, the symbol or symbols applied to path
5
I
1
, and so on. Each of paths
5
I lead to transmission channel
4
, within which the symbols are resequenced and over which the symbols are serially communicated.
The varying delay among paths
5
I has a regular pattern in conventional convolutional interleaving. In the example of
FIG. 1
, path
5
I
0
involves no delay, such that the symbol or symbols applied thereto by demultiplexer
2
are immediately forwarded to transmission channel
4
. Path
5
I
1
involves a delay of B′ symbols, where B′ corresponds to the number of symbols applied to each path
5
I by demultiplexer
2
in a given vector; the symbol or symbols applied to path
5
I
1
in a first cycle are thus communicated to transmission channel
4
in the next cycle. Path
5
I
2
involves a delay of 2B′, such that the symbol or symbols applied thereto in the first cycle are communicated to transmission channel
4
two cycles later, and so on, up until path
5
I
n−1
, which involves a delay of (N−1)B′.
The number B′ corresponds to the ratio of the total number of symbols communicated in a vector (B) to the number of symbols upon which the appropriate decoding technology (e.g., Reed-Solomon) operates (N). Typically, in the Reed-Solomon coding case, N symbols a recommunicated in a single vector, such that B=N, and thus B′=1. In this case, therefore, N symbols are demultiplexed by demultiplexer
2
in a given operation, and one symbol is applied to each of N paths
5
I
0
through
5
I
N−1
.
Because of the varying delays of N paths
5
I, the system of
FIG. 1
executes convolutional interleaving of the symbols to be communicated over transmission channel
4
. Consider, for the sake of explanation, a

Affiliated with

Also associated with

Rating

Efficient memory addressing for convolutional interleaving does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient memory addressing for convolutional interleaving, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient memory addressing for convolutional interleaving will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2844335