International Business Machines Corporation

Sumio Morioka

Yasunao Katayama

Toshiyuki Yamane

Akashi Satoh

Gang Zhang

To provide a high-speed combinational circuit including an S-Box and a method for creating an RO-BDD that defines a configuration of the combinational circuit. The combinational circuit includes a number of independent selector groups for each generating an output bit separately, the number corresponding to number of the output bits, and a driver chain for supplying a primary input to each of the selector groups, in which each of the selector groups includes a plurality of selectors connected to each other to form a number of stages, the number of stages being equal to or less than number of bits of the primary input, and a select signal for the selectors in each stage is driven by one primary input.

Combinational circuit, encryption circuit, method for constructing the same and program

A signal processing method for a digital signal comprising the steps of: establishing a Yule-Walker equation having the following form by using a matrix that includes, as components, the elements of a Galois field GF(2), and a vector that includes, as components, the elements of the Galois field GF(2) employing Jacobi's formula to obtain the solution of the above equation by the calculation of determination of symmetric matrices; determining the number of errors to be the maximum matrix size that corresponds to the obtained solution that is not zero; and determining whether the number of errors equals the maximum number of correctable errors.

Signal processing method, signal processing system, program for signal processing, and computer-readable storage medium on which this program is recorded

A combinational circuit comprises: a plurality of multipliers, independently performing two or more multiplications for coded digital signals in a Galois extension field GF(2) (m is an integer equal to or greater than 2), wherein the multipliers include an input side XOR calculator, an AND calculator, and an output side XOR calculator, and wherein the multipliers share the input side XOR calculator. Further, according to the present invention, these multipliers each include an adder connected between an AND calculator and an output side XOR calculator, wherein the output side XOR calculator is used in common, and wherein the outputs of the AND calculators in the multipliers are added by the adders, and the addition results are calculated by the output side XOR calculator that is used in common.

Combinational circuit, and encoder, decoder and semiconductor device using this combinational circuit

A decoding circuit used to correct an error in a digital signal includes: an input unit for entering coded digital signals ID in parallel in accordance with the number of interleaved codes; a processor including an error locator polynomial calculator and an error value polynomial calculator for processing data obtained serially from the interleaved codes that are received by the input unit; and an output unit for correcting errors by employing the output data that are received from the processor and the digital signals ID, and for outputting in parallel the obtained digital signals OD, for which an error has been corrected by a linear calculation on a Galois field, in accordance with the number of interleaved codes.

Decoding circuit, and decoder, decoding method and semiconductor device that use the decoding circuit

A multiplication module, including a first input unit and a second input unit, for multiplying m bits of data in a Galois field GF(2)(m&#x2267;1), includes: first and second power arithmetic units for receiving the first m bits of data from the first input unit; a first multiplication unit for receiving the first m bits of data and the output of the first power arithmetic unit; a second multiplication unit for receiving second m bits of data from the second input unit and the output of the second power arithmetic unit; a selection unit for receiving an output signal from the second multiplication unit and the second m bits of data; and a control unit for outputting a control signal to the first power arithmetic unit, the second arithmetic unit and the selection unit, wherein the first power arithmetic unit receives a first control signal, the second power arithmetic unit receives a second control signal, and the selection unit receives a third control signal, for controlling the output of the selection unit, while the first multiplication unit outputs a first output signal, and the selection unit outputs a second output signal.

MULTIPLICATION MODULE, MULTIPLICATIVE INVERSE ARITHMETIC CIRCUIT, MULTIPLICATIVE INVERSE ARITHMETIC CONTROL METHOD, APPARATUS EMPLOYING MULTIPLICATIVE INVERSE ARITHMETIC CIRCUIT, AND CRYPTOGRAPHIC APPARATUS AND ERROR CORRECTION DECODER THEREFOR

A system having multiple encoders of different maximum error correction capability, which reduces the entire size of the system by allowing most of the system to be shared among these encoders. This is accomplished by using an encoder that is capable of calculating parities of 2 or more kinds of bit numbers with different error correction capability. The system includes a circuit that generates a modified word by assigning a predetermined value to input an information word; and a circuit that generates an intermediate signal &ldquo;u&rdquo; by a linear operation using a modified word and matrix &ldquo;P&rdquo;. These circuits are combined with linear operation circuits for generating value of parity p , . . . , p , each of whose bit number is different, by a linear operation using all or part of the intermediate signal and matrixes Q , . . . , Q respectively.

Shared encoder used in error correction having multiple encoders of different maximum error correction capabilities

A Reed-Solomon decoder that can correct t errors or fewer which includes: a syndrome calculation circuit for calculating syndromes S (J&equals;0, 1, . . . , 2t&minus;1) using the first codeword Y (i&equals;0, 1, . . . , n&minus;1) (so-called received codeword) that may include errors; and a coefficient calculation circuit for, by using the syndromes S , calculating coefficients &Lgr; (k&equals;1, . . . , e) of an error-locator polynomial. The coefficients &Lgr; correspond in number to e estimated errors (e&lE;t<n). The syndromes S , calculating coefficients Er (1&equals;0, . . . , &ecirc;) (&ecirc; can be as small as O(e)) of an error polynomial, and the coefficients Er correspond in number to the e estimated errors. An error value calculation circuit for calculating error values E by using the coefficients Er of the error polynomial, and for using the coefficients &Lgr; of the error-locator polynomial to generate a signal concerning the error value E to be used and an output circuit for using the first codeword Y and the error value E , which correspond to the signal used to calculate the second codeword W (so-called source codeword) in which the estimated errors are corrected. Since e&lE;t<n, and since there are e coefficients &Lgr; and e coefficients Er , the number of calculations performed by, and the sizes of the coefficient calculation circuit and the error value calculation circuit are reduced. Specifically, since the coefficient calculation circuit requires gate-consuming non-linear operations in order to calculate the coefficients &Lgr; and Er , the effects achieved by such a reduction are greater.

Growing community of inventors

Yamato, Japan

Sumio Morioka