公开(公告)号：GB1292772A

公开(公告)日：1972-10-11

申请号：GB1781971

申请日：1971-05-28

Applicant: IBM

Inventor： RAVIV JOSEF ,  WESLEY MICHAEL ANDREW

IPC: H03M5/00 ,  H03M7/30

Abstract: 1292772 Code conversion INTERNATIONAL BUSINESS MACHINES.CORP 28 May 1971 [10 Aug 1970 8 Sept 1970] 17819/71 Heading G4C Variable-length codes and corresponding fixed-length codes are held in a store which may be accessed in response to a given variablelength code and fixed length code to obtain the corresponding fixed-length code and variablelength code respectively. The store may be an associative array each word location of which contains corresponding variable- and fixedlength code pair and a length count indicating the number of significant bits in the V-L code. Associative memory, Fig. 2.-Each cell includes a FF22 storing a binary data bit and a FF24 which is set at 1 if the data bit is significant and set at 0 to represent a "don't care" state, the cells of each word being set by a common word select line 32, and 1, 0 and "don't care" lines 26, 28, 30. Associative interrogation pulses are supplied on pairs oflines 44, 46 so that, for a cell storing a significant bit, a mismatch output is obtained from gate 40 or 42 when the stored bit in FF22 does not correspond to the interrogate bit on lines 44, 46 to set a word match indicator (MI) to the 0 state. A read pulse on line 66 is routed by the MI remaining in the 1 state and indicative of a matching word to gate out all bits of the matching word (VL, FL and length count fields) on to lines 74, 76. Encoding.-Parallel-bit fixed-length (ID) code to serial-bit variable length (VL) code. The number of ID bytes to be encoded is entered in byte counter 80, Fig. 3B, and clock E1 gates the first of these ID bytes into argument register 100 and resets the match indicators of associative memory AM to the "one" state. Clock E2 reads out argument register 100 on to the associate lines (44, 46) of the ID field in AM. Clock E3 pulses read line 66 to read out the matching word (all three fields) into data register 120, and decrements byte counter 80. Clock E4 gates out the right-hand bit of the V-L field to the output device and clock E5 shifts register 120 one place to the right and decrements the length field counter section of register 120. Clock E6 tests the state of the length counter at gate 138, Fig. 3B, to cause return to E4 followed by read out of the next bit from register 120 as before, until the length counter reaches 0, when a return to E1 made to repeat the process for the next ID byte to be encoded. When all bytes have been encoded, counter 80 reaches 0 and an END signal is produced at clock E6 time. Decoding serial-bit V-L code into parallelbit ID code. Byte counter 80 is loaded with the number of codes to be decoded and clock D1 resets the length counter section of register 120 to all zeros, representing 16-the maximum word length. Clock D2 gates the first V-L code bit to argument register 178 and decrements the length counter. Clock D3 tests the state of the length counter at gate 202, Fig. 3B, and D4 shifts register 178 one place to the right and causes return to D2 to enter the next V-L code bit in register 178 until, when all 16 bits of the V-L field have been entered, the length counter is again at all zeros and D3 causes a step to D5 to reset the match indicators to the 1 state. Clock D6 reads out the argument register 178 on to the associate lines (44, 46) of the V-L field in AM and clock D7 reads out the matching word (all three fields) into data register 120 and decrements the byte counter 80. Clock D8 gates out the ID code from register 120 and clock D9 shifts register 178 one place to the right and decrements the length counter. Clock D10 gates in the first bit of the next V-L code to be decoded into register 178 and clock D11 tests the state of the length counter -at gate 248, Fig. 3B. Operation under clocks D9-D11 is repeated until the length counter is at 0 when D11 causes a return to D5 to decode the next V-L code now fully in register 178 or to produce an END signal. Copy mode.-Some data compaction may be sacrificed to save on the size of the memory AM by arranging the system to handle only the most frequently occurring V-L codes. Thus, AM may have only 150 say locations for matched V-L, ID pairs plus an additional location for a copy code (in the V-L field) and an ID code different to all the others. Since only the most frequent (shorter) V-L codes are stored, a smaller number of bits per word is also required in AM. In an encoding operation when no ID match is found, the copy code is read out from register 120 followed by the ID code from the argument register 100. In a decoding operation incoming codes which may include copy plus ID codes are entered in argument register 178, and if a copy code is present it is erased by shifting register 178 and the ID code which is then at the right-hand end of this register is read out in parallel.

公开(公告)号：DE1925428A1

公开(公告)日：1970-01-29

申请号：DE1925428

申请日：1969-05-19

Applicant: IBM

Inventor： ALDEN MELAUGHLIN JOHN ,  RAVIV JOSEF

IPC: G06K9/80 ,  G06K9/08

Abstract: 1,223,348. Pattern recognition; calculating. INTERNATIONAL BUSINESS MACHINES CORP. 25 April, 1969 [21 May, 1968], No. 21209/69. Headings G4A and G4R. A pattern recognition system compares an effective Nth order self-scale function or Nth order hybrid self function of an unknown pattern with the same function of a reference pattern, or generates and raises to the Nth power the cross-correlation of unknown and reference pattern data. Data from a raster scan of the unknown pattern is stored in a first utility memory as data with associated X and Y co-ordinates, the centre of gravity of the pattern is calculated from this information and the co-ordinates are then altered so as to be relative to this centre of gravity as origin (displaced by a constant vector so that no co-ordinate will be negative). The data is then transferred to a second utility memory in such a way that the results simulate an annular scan of the pattern with exponentially increasing radius, using addresses read from the second memory to address the first. Apart from these addresses and the transferred data, the second memory contains polar coordinates of the data. The data and polar coordinates are transferred to an input signal memory and from there the data is crosscorrelated with reference data from L reference memories in turn, where L is the number of possible patterns, as follows. For a given reference memory, the locations of a correlation result memory are addressed in turn, and for each, each item of data in the input signal memory is multiplied by data obtained by addressing the reference memory with the concatenation of the polar co-ordinates associated with the data item in the input signal memory, each incremented by a respective quantity preloaded in the addressed location of the correlation result memory and either changed, if necessary, to lie in a certain range or preventing addressing if outside a certain range. The results of the multiplications are accumulated, then stored in the addressed location of the correlation result memory. The correlation results for a given reference pattern are then either each raised to the Nth power and then accumulated, or each raised as a power to 2 and then accumulated, or the largest is selected. Whichever of these three non-linear operations is used, a result is obtained for each of the reference patterns. Each such result is divided (or multiplied) by a respective normalization factor from a memory to give a quantity, the largest of such quantities from the reference patterns considered so far, being passed together with reference pattern identifiers, to an output memory for a recognition decision. In the case of the third non-linear operation above (" largest "), quantities in effect selected from the correlation result memory indicating size, rotation &c. are also passed. The raising to the Nth power is done by repeated multiplication by itself, whereas the raising as a power to 2 is done by loading a shift register with 000 ... 0001, and left-shifting while decrementing the quantity to be raised, to zero. Autocorrelation may replace the centre of gravity manipulations. The cross-correlation may be done with the original pattern data. During a learning mode using reference patterns, the reference memories are loaded with what they would be correlated with in recognition mode, and the normalization factor memory is loaded with the square-roots of the results from the non-linear operation used (on the reference patterns). The operations above are equivalent to evaluating similarity functions which are the normalized integral of the product of the Nth order autocorrelation functions of the unknown pattern and a reference pattern (translation invariant), or similar quantities using Nth order self scale functions (which are integrals invariant to scale change) or Nth order hybrid self-functions (which are integrals invariant to scale and rotation) in place of the Nth order autocorrelation functions, or normalized quantities involving sums of exponentials of sums of products, or normalized quantities involving maxima of sums of products. Integrals are evaluated as sums, operations being electric digital throughout. The mathematical expressions are given in the Specification.