Combinatorial polynomial multiplier for galois field 256...

Details Combinatorial polynomial multiplier for galois field 256... Combinatorial polynomial multiplier for galois field 256...

1996-10-03

2002-10-29

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06473779

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to a technique for multiplication in Galois Field arithmetic and more specifically to a multiplier for a Galois Field 256 arithmetic. Galois Field 256 arithmetic multipliers have a specific application in decoders for Reed-Solomon codes.
Reed-Solomon codes are used as error correcting codes in a wide variety of commercial applications such as compact discs, high speed cable modems, modulation systems for set-top box applications and the current HDTV standard. These codes are typically applied to data transmissions in which the data is transmitted by bytes, thus the interest is in Galois Field 256 arithmetic, as this accommodates 8-bit variables. In Galois Field 256 arithmetic, bytes are also called symbols. The Digital Audio-Visual Council (DAVIC) standard specifies a 204/188/8 Reed-Solomon code. The 204, also known as N, is the number of symbols in the channel codeword. The 204 symbols broadcast over the channel is called a frame. The 188, also known as K, is the number of symbols of information in the source codeword. The 8, also known as T, is the number of errors that can be corrected; the number of errors being equal to one-half of the difference of N and K. In this case, 188 bytes of data has 16 bytes of error correcting codes added to generate 204 bytes per frame. This code can correct for 8 errors in the frame. The correction involves the determination of both the location and the magnitude of the error. A problem with Reed-Solomon codes is that it forces the burden of computation upon the decoder, rather than on the encoder. For example, the code required in the DAVIC standard requires 16 Galois Field multiplications in the encoder and 2,550 Galois Field multiplications in the decoder. In view of the fact that the multiplications performed at the encoder are normally at the broadcast or recording studio level, the cost of such equipment can be amortized over the number of listeners/viewers. However, the decoder must be owned by each listener/viewer where its cost becomes a significant issue.
FIG. 1
shows a typical application of a decoder for Reed-Solomon codes employing Galois Field 256 arithmetic shown generally as
100
in FIG.
1
. The signal to be decoded is applied to a delay
102
and a decoder circuit
106
via line
104
. The purpose of delay
102
is to delay the signal the amount of time it takes for the decoder
106
to perform the decoding operations. The delay
102
may be a RAM of suitable length, for example. The output of the delay
102
is applied to a circuit
112
as is the output of decoder circuit
106
via line
110
. Circuit
112
contains a RAM and the Galois Field arithmetic circuitry to make the corrections to the stored data where errors have been detected. This could involve Galois Field addition of an error correction to the data containing the error, for example. If it would be desirable that the delay be 100 clock cycles, for example, then the RAM
102
would store 100 bytes, after which the data would be loaded into the RAM of circuit
112
. The RAM of circuit
112
would have a capacity of 204 bytes, for example, under the DAVIC standard. As the RAM reaches capacity, errors on line
110
would be output to the RAM of circuit
112
, in order to correct the errors. By the time the 204 clock cycles of the frame have been completed, all of the entries into the RAM have been made and all the corrections to those entries have also been made. Then data is taken from the top or zero address of the RAM and output to a display (not shown) on line
114
and a new entry is applied to that slot via line
108
and the process repeats. Longer delay times increases the latency of the signal and the size of the RAM that is required for the delay
102
.
FIG. 2
shows a prior art polynomial multiplier for Galois Field 256 arithmetic which takes 8 clock cycles to complete the computation. The notation “(
7
:
0
)” refers to bits
7
-
0
of the variable A. The circuit comprises of two multiplexers having inputs of A (
6
:
0
) and B (
7
:
0
) respectively. The output of multiplexers on lines
214
and
216
are input into registers
220
and
222
respectively. The output of registers
220
and
222
on lines
226
and
230
are fed back to multiplexers
210
and
212
via lines
206
and
208
respectively. Lines
226
and
230
are also fed into multiplexers
238
and
240
, respectively. The second input to multiplexer
238
is A (
7
) on line
228
and the second input to multiplexer
240
is B (
7
:
0
) on line
232
. The output of the multiplexers
238
and
240
on lines
244
and
246
is input into A-block
248
to produce the result C (
7
:
0
) on line
250
. Line
250
is coupled into X-block
254
via line
250
. The output of X-block
254
on line
218
is the result of Y(
7
:
0
) which is fed back to register
224
the output of which is fed via line
234
to multiplexer
242
, which also has an input of (0) on line
236
. The output of multiplexer
242
on line
252
is Y
1
(
7
:
0
) which is also input into X-block
254
. The first cycle ANDs the most significant bit of A with B(
7
:
0
), XORs the result with Y(
6
:
0
), XORs the primitive polynomial and stores the result. The A register stores the one-bit left-shifted result. The least significant bit is loaded with a 0. These operations are repeated seven more times which produces the file output. This circuit is well known in the prior art.
Returning to
FIG. 1
, if the delay
102
is desirably no more than 100 clock cycles, for example, and the DAVIC standard is applied, the number of polynomial multipliers for the Galois Field 256 arithmetic that is required is:
2,550 divided by 100=25.5=26
However, the fact that the prior art multipliers require 8 clock cycles to perform a single multiplication, means that 8 times that number of multipliers is required, 8 times 25.5 equalling 204 multipliers in a single decoder. It must be remembered that each CD player, set-top box, etc., that contains a Reed-Solomon decoder must have this number of Galois Field multipliers. The number of multipliers can be decreased by increasing the delay of the delay element
102
, but this increases the size of the RAM that is required and increases the latency of the signal. This problem is exasperated by the fact that realizing Reed-Solomon codes for correcting video signals will require a data rate of 5 megabytes per second. If the techniques of the prior art are utilized, this would require a clock frequency of 40 MHz for a single clock cycle multiplier.
Polynomial multipliers for Galois Field arithmetic are very different from multipliers for infinite field variables and are non-intuitive. This can be seen from a simple multiplication example involving Galois Field 4 arithmetic, shown in Table 1. Galois Field 4 arithmetic is illustrated because the table has only 16 entries whereas a table for Galois Field 256 arithmetic has 65,536 entries.
TABLE 1
X
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
3
1
3
0
3
1
2
Galois Field 4 arithmetic involves the numerals 0,1,2 and 3 only. It takes only a quick glance at Table 1 to realize how different Galois Field arithmetic multiplications are. According to the table, multiplication of 3×3 yields a result of 2 which is quite astonishing to those not familiar with Galois Field arithmetic.
Galois Field 256 arithmetic contains a set of 256 numbers from 0 to 255. This produces the 65,536 possible combinations referred to above. The large number of possible combinations make other solutions such as the required number of look-up tables (LUTs) impractical. Accordingly, there is a need for a low cost, high speed Galois Field 256 multiplier which is particularly applicable to a decoder for Reed-Solomon codes.
SUMMARY OF THE INVENTION
It is a general object of the present invention to provide a method and apparatus for Galois Field multiplication.
It is a further object of the present invention to provide a method and apparatus for Galois Field 256 arithmetic multiplication.
A still further object of the present inventio

Affiliated with

Also associated with

Rating

Combinatorial polynomial multiplier for galois field 256... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Combinatorial polynomial multiplier for galois field 256..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial polynomial multiplier for galois field 256... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2990571