Patent GB-1048435-A (GB)
Title: Information handling system
IPC: G06F17/30
Filed: 1964-03-19
Abstract: 1,048,435. Key to address transformations. INTERNATIONAL BUSINESS MACHINES CORPORATION. March 19, 1964 [April 12, 1963], No. 11579/64. Headings G4A and G4C. A system with an addressable data store receives a key which is a member of a group array which has been subjected to a coset expansion, and derives from it a coded signal determined by the coset leader of the coset including the key, and derives an address from the coded signal and key. The invention is designed for use when n-bit codes are to be used for calling data from a memory of less than 2<n> locations. Only a selection of the 2<n> possible codes (called " keys ") are used (and are therefore in general non- consecutive) and are converted into shorter parity check sequences which are consecutive. These sequences are the memory addresses. The set of 2<n> possible codes forms an Abelian group with respect to modulo-2 addition of corresponding bits (as "product "). A subgroup of 2<k> codes is chosen and written as the first row of a group array. The other rows of the array are built up successively by taking for each row any one of the 2<n> possible codes which has not occurred in any previous row and forming the " product " (as defined above) of it with all codes of the first row. 2<n-k> rows (termed "cosets ") are formed and exhaust the group without duplication of codes. A parity check sequence for a given code consists of (n-k) bits each of which is the modulo-2 sum of a certain selection of the bits of the code (e.g. the first and third). Corresponding bits in the parity check sequences for different codes use the same selection. It happens that all codes in a given coset (or row) of the group array will have the same parity check sequence and the parity check sequences for the different rows will be consecutive (considered as binary numbers) and unequal, if the selections to be used are determined according to a method described in the Specification (which starts with the chosen subgroup). In the embodiment of Fig. 1 (not shown), keys in any given column of the group array are at closer distances from each other than from keys in other columns. The parity check sequence of (n-k) bits derived from the n-bit key is used to address an auxiliary memory holding the coset leaders of the group array. The term coset leaders refers to the identity element of the group, from the first row (coset) of the array, and the element in each of the other rows obtained from the identity element during the building up of the array (see above). Each of the k lowest order bits of the addressed coset leader is added modulo-2 to the corresponding one of the k lowest order bits of the key, the result being used to read out a sequence of memory locations in a main memory to an output punch. This sequence contains all information records having keys within a given distance of each other. If there is more than one key per column of the group array, zeros are added to the output of the adding unit before application to the main memory. On the other hand, this is not done if there is only one key per column. The latter situation is useful in case of errors in the key since the distance property ensures that even slightly erroneous keys still correspond to the same address. A further embodiment (Figs. 2, 3, not shown) utilizing the polynomial-type error-correcting Fire code is somewhat similar to the first except that the second modulo-2 adding is done serially by bit rather than in parallel and logic replaces the auxiliary memory.