公开(公告)号：CA721421A

公开(公告)日：1965-11-09

申请号：CA721421D

Applicant: IBM

Inventor： HANAN MAURICE ,  PALERMO FRANK P ,  RAVER NORMAN ,  SCHAY GEZA

公开(公告)号：DE1474039A1

公开(公告)日：1968-12-12

申请号：DE1474039

申请日：1964-04-08

Applicant: IBM

Inventor： HANAN MAURICE ,  PANTELEONE PALERMO FRANK ,  RAVER NORMAN ,  HEIGHTS YORKTOWN ,  SCHAY GEZA

IPC: G06F17/30

Abstract: 1,030,253. Addressing memories; code conversions. INTERNATIONAL BUSINESS MACHINES CORPORATION. March 19, 1964 [April 12, 1963], No. 11582/64. Headings G4A and G4C. In a data storage apparatus, a set of keys is mapped on to a smaller set of addresses by means for performing an algebraic transformation on each of said keys to provide a respective address, whereby keys separated by a Hamming distance of less than a predetermined amount are provided with different addresses. Referring to Fig. 1, a key K=(k0, k1, k2 ... k29) shifted into register 12 is converted into an address A=(a0, a1 . . . a4). Each element ki, ai is represented as six bits in parallel (and is an element of a Galois field-see Table I of the Specification). If the key K and address A are represented as polynomials K(X) and A(X) (the elements ki and ai being the coefficients of the terms thereof) the conversion may be represented where G(X) is a suitable (e.g. Bose-Chaudhuri) generator polynomial and Q(X) a quotient. The elements ki of the key K are shifted in turn into a chain of flip-flop sets 20-1 to 20-5, each set comprising six flip-flops. An element shifted out of set 20-5 goes to each of multiplier units 40-1 to 40-5, each of which comprises singlebit modulo-2 adders (i.e. exclusive-or gates) so connected that the output of the multiplier unit equals the input multiplied by one digit (coefficient) of the generator polynomial G(X). Each of the six bits of the output of each multiplier unit 40-1 to 40-5 is added modulo-2 to the corresponding bit of the next element ki approaching a corresponding flip-flop set 20-1 to 20-5, at a corresponding set of six modulo-2 adder units 32-1 or &c., the result of the addition entering the flip-flop set 20-1 or &c. When the last element k0 is shifted out of register 12, a counter and delay unit 15-2, after a short delay, enables a random-access memory 16 to respond to the contents of the fllip-flop sets 20-1 to 20-5, these being the required address. The multiplier units 40-1 to 40-5 are different from each other and have internal structures simulating the multiplicand, but as a modification each may be the same, comprising AND-gates and modulo-2 adder units and being supplied with the multiplicand over a set of six wires from a storage register. The key to address conversion may equivalently be represented by a suitable matrix [tij], thus: the matrix elements tij (each being six bits in parallel) being passed in turn to a single multiplier via a set of six delay line stores (one per bit position) and a six-bit register. The multiplier is also supplied with the key elements kj in turn from a shift register. When a given key element kj is presented it is multiplied by the appropriate five tij in turn, the answers being sent to five six-bit accumulators respectively. At the end, each accumulator is thus left storing one of the address elements ai (Figs. 8, 9, not shown).