International Business Machines Corporation

Akashi Satoh

Hideto Niijima

Yoshinao Kobayashi

Takashi Toyooka

Yoshinori Sakaue

Seiji Munetoh

Kohji Takano

Koichi Kamijo

Sumio Morioka

Gang Zhang

Hideto Nijima

A multiplier circuit is disclosed including a Wallace tree block and a carry propagation adder. The Wallace tree block includes a sum calculation block adding partial products for each digit and a carry calculation block adding carries obtained in the addition by the sum calculation block. In the case of multiplication over an extension field (finite field GF(2)) of two, a result of calculation by the sum calculation block is outputted. The carry propagation adder adds the result of calculation by the sum calculation block and a result of calculation by the carry calculation block. In the case of multiplication for integers (finite field GF(p)), a result of calculation by the carry propagation adder is outputted.

Multiplier and cipher circuit

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

Provided is a content play back apparatus including: a play back means for playing content including audio or video; a play list managing means for managing a play list which is a list of identification information on content previously played by the play back means; a blacklist acquiring means for acquiring a blacklist which is a list of identification information on content illegally copied in the past; and a play back restricting means for restricting content play back of the play back means when any of identification information included in the play list is included in the blacklist.

Content play back, information processing, and play back restriction

A circuit and a method for solving the Montgomery multiplier bottleneck problem encountered during a memory access using two ports or single port general-purpose memories is described. A first and a second memory are provided such that variables that are stored in one memory must be read for an operation to be recorded in the second memory. Thereafter, during a reading cycle corresponding to a pipeline process, certain of the variables are read from the first memory and are loaded in the predetermined register while the other variables are read from the second memory and are loaded in the remaining registers.

Arithmetic circuit to increase the speed of a modular multiplication for a public key system for encryption

A carry skip adder has a plurality of ripple adders, in which at least one part of the plurality of ripple adders is divided into a plurality of groups, and a carry signal is transferred from one group to one upper group. In addition, a circuit for calculating C&equals;C &plus;F*C is included, in which the C denotes a carry signal from the one group to the one upper group, and the F denotes a signal indicating whether or not outputs of all adders in the one upper group are 1s, and the C denotes a carry signal associated with the most upper ripple adder in the one upper group. In a group including two or more ripple adders, a plurality of ripple adders in the group are organized into a plurality of sub-groups, and a carry signal is transferred from one sub-group to one upper sub-group, a circuit for calculating C &equals;C &plus;F *C is included, in which C denotes a carry signal from one sub-group to the one upper sub-group, and F denotes a signal indicating whether or not outputs of all adders in the one upper sub-group are 1s, and C denotes a carry signal associated with the most upper ripple adder in the one upper sub-group.

Carry skip adder

An apparatus to calculate a remainder of B,modulo n at high speed with minimum hardware resources, while securing safety of a key comprises: a first circuit to execute a process of calculating B (mod n) and holding the calculation result B,and to repeat a process of shifting a holding value and calculating a value congruent to the shifted holding value modulo n and holding the calculation result; a first register for storing the B,as an initial value; a second circuit to cumulate the calculation result of the first circuit when a value of a bit at a predetermined position of the first register is equal to 1; a second register to store 1 as an initial value; a C output circuit to output C; a third circuit to cumulate the calculation result of the first circuit when an output value from said C output circuit is equal to 1 and a value of a bit at a predetermined position of the second register is equal to 1. The bit at the predetermined position of the first register and the second register shifts from LSB to MSB of their stored values. When a process for MSB of a value stored by the first register ends, a value congruent to the cumulated result in the second circuit modulo n is set as the holding value and stored into the first register, the output of the C output circuit changes to a value shifted from LSB to MSB of the C, and when the output of the C output circuit is 1, a value congruent to the cumulated result in the third circuit modulo n is stored in the second register.

Apparatus for calculating of Bc (mod n) with repeatedly shifting a holding value

A carry skip adder comprises a plurality of ripple adders, wherein at least one part of the plurality of ripple adders is divided into a plurality of groups, and a carry signal is transferred from one group to one upper group. In addition, a circuit for calculating C&equals;C,&plus;F*C,is included, wherein the C,denotes a carry signal from the one group to the one upper group, and the F denotes a signal indicating whether or not outputs of all adders in the one upper group are is, and the C,denotes a carry signal associated with the most upper ripple adder in the one upper group. In a group including two or more ripple adders, a plurality of ripple adders in the group are organized into a plurality of sub-groups, and a carry signal is transferred from one sub-group to one upper sub-group, a circuit for calculating C,&equals;C,&plus;F,*C,is included, wherein the C,denotes a carry signal from the one sub-group to the one upper sub-group, and the F,denotes a signal indicating whether or not outputs of all adder in the one upper sub-group are is, and the C,denotes a carry signal associated with the most upper ripple adder in the one upper sub-group.

Apparatus method for calculating the remainder of B.sup.C modulo n at high speed with minimum hardware resources, while securing the safety of the key in a cryptographic system. The apparatus comprises circuitry including registers for executing an initial and normal cycles, cumulating and storing the calculation result of each cycle and for outputting from a least significant bit. The initial cycle of the calculation includes a step of calculating a remainder of an m-bit input modulo n and a step of holding the result of the calculation. The normal cycle of the calculation includes a step of doubling the result of the calculation, and calculating a remainder of the doubled result of the calculation modulo n and a step of holding the next result of the calculation and for repeatedly executing the normal cycle m-2 times after the first normal cycle. The calculation result of each previous normal cycle is used in each successive normal cycle.

Apparatus and method for calculating B.sup.c (mod n)

To compress data at high speed, a search character is input to a write buffer 56 in sequence. Each of content addressable memory (CAM) cell rows compares the search character with character data stored therein and outputs the comparison result through a match line MATCH to a comparison result control circuit 60 every time. The comparison result is held in sequence to latches 82 and 84. When a signal ORFB input to a signal generation circuit 64 is low, the circuit 86 outputs the logical product between the output of the latch 82 and the output of the latch 88 of the preceding stage to a priority encoder 74 through a latch 88 and also to an OR circuit 90. When the signal ORFB is high, the circuit 86 outputs the logical product between the output of the latch 82 and the output of the latch 84 of the preceding stage to the priority encoder 74 through the latch 88 and also to the OR circuit 90. The encoder 74 outputs the logical sum of input signals as a match signal MSIG0 representative of the comparison result, and likewise an encoder 76 outputs the logical sum of input signals as a match signal MSIG. The signal output from the OR circuit 90 is input through a latch 92 and an OR circuit 94 to each signal generation circuit 80 as a signal ORFB. With this arrangement, the length of a path through which a signal passes in one cycle of a clock is reduced to half and therefore data compression can be performed at high speed.

Search circuit for data compression

An array of memory cells is physically divided into a data area and a tag area so that respective parts of the two areas share a word line but can be separately erased en bloc. The data area and tag area sharing one word line constitute a single logical unit. In the logical unit, the tag area stores location information for defective memory cells in the corresponding data area. On the basis of this information, the system avoids the use of the defective memory cells. The defective memory cell information is programmed in a test step performed after chip manufacture and, at the same time, ECCs are generated for the defective memory cell information and written to the tag area. Furthermore, the system is informed of the invalidity of the data area that shares a word line with a tag area by writing predetermined data to the tag area. Even when the data area is erased en bloc, the tag area is not erased and the defective memory cell information is retained there.

Flash-erase-type nonvolatile semiconductor storage device

With the present invention, the page table of the program code non-continuously placed in an external storage device using randomly accessible and rewritable memory is built into an executable sequence in a virtual address space of the CPU according to the execution order. By referring to the address translation tables, including the page table, the system is able to read the program from the external storage device, thereby executing the program. Therefore, the program can be executed without being loaded into main memory. Furthermore, the program and data can be managed without distinction. Further, with the randomly accessible memory according to the present invention, since a sequence of real addresses of the CPU are assigned to the data area, control over the direct execution of the program can be simply achieved. Furthermore, since data and ECC parity can also be read and written sequentially, the system has good compatibility with a hard disk system. Since the data and Ecc parity are present on the same word line and can be accessed without changing the page address, simple control is achieved.

Control method and apparatus for direct execution of a program on an

A timing control signal SR is made low to switch on a P-MOSFET and switch off an N-MOSFET, and with an N-MOSFET as a boundary, a voltage V.sub.MATCHI on the side of a NOT circuit of a match-line is pulled up to a power supply voltage V.sub.DD. During this, a comparison operation is done in a content addressable memory cell, and an N-MOSFET is switched on or off according to the result of comparison. Next, the control signal SR goes to a logic high level, so the P-MOSFET is switched off and the N-MOSFET is switched on. As a result, if the N-MOSFET is on, the voltages V.sub.MATCHI and V.sub.MATCH will be reduced to a ground level, but the through current is prevented because the P-MOSFET is off. If the N-MOSFET is off, the V.sub.MATCH will be pulled up to V.sub.DD -V.sub.tn (V.sub.tn is the threshold voltage of the N-MOSFET), the V.sub.MATCHI will be held to V.sub.DD by the NOT circuit and the P-MOSFET, and a signal representative of a result of comparison will be output from the NOT circuit. Also, by the interval of the N-MOSFET, the parasitic capacitance of the portion on the side of the content addressable memory cell of the match-line with the MOSFET as a boundary disappears from the portion on the side of the pull-up means from the portion on the side of the NOT circuit with the voltage drop element as a boundary, so the pull-up of the portion on the side of the NOT circuit with the MOSFET as a boundary becomes fast.

Content-addressable-memory control circuit

An array of memory cells is physically divided into a data area and a tag area so that respective parts of the two areas share a word line but can be separately erased en bloc. The data area and tag area sharing one word line constitute a single logical unit. In the logical unit, the tag area stores location information for defective memory cells in the corresponding data area. On the basis of this information, the system avoids the use of the defective memory cells. The defective memory cell information is programmed in a test step performed after chip manufacture and, at the same time, ECCs are generated for the defective memory cell information and written to the tag area. Furthermore, the system is informed of the validity of the data area that shares a word line with a tag area by writing predetermined data to the tag area. Even when the data area is erased en bloc, the tag area is not erased and the defective memory cell information is retained there.

This is a variable length data search apparatus which uses a latch, added to each word of a cell array. In this apparatus, the search operation is self controlled by using the previous matching signals stored in the latches. A character string (ABCA), from a data string (BABCABB . . . ), is stored, in order, in an associative memory containing, e.g., six rows having addresses 1 to 6, and the first character of the data string is sent to a buffer and a comparison is made. This sequence is repeated for each character but now the comparison is made only at the cell rows addresses which are adjacent the cell rows, which matched the previous character. This means that even if the length of the search character string is a variable length, only the number of times the comparison operation is repeated varies and this permits the search to be completed in an extremely short time as compared to the prior art. A data compression circuit based on the LZ1 algorithm is also disclosed and uses; a data input control circuit, the variable length search apparatus disclosed above; a write address controller, and address register; a garbage address controller; a matching length counter and a compressed data output circuit.

Growing community of inventors

Yamato, Japan

Akashi Satoh