Patent GB-1190609-A (GB)
Title: Data Compression System.
IPC: H04N1/417
Filed: 1967-12-27
Abstract: 1,190,609. Pictorial data transmission systems. INTERNATIONAL BUSINESS MACHINES CORP. 27 Dec., 1967 [3 Jan., 1967], No. 58603/67. Headings H4F and H4P. Binary data representing pictorial information derived by the line-by-line scan of a picture is reduced in redundancy by a first system of run-length encoding whereby there are formed binary words in sequences each corresponding to a line scan of the picture, a second system of run-length encoding being employed which operates by comparing words in corresponding positions in successive sequences so as to form a final signal which represents the picture with redundancy reduced in both the horizontal (line scan) and vertical directions. The broad form of the arrangement is shown in Fig. 2 where the first run-length encoder 9 supplies word sequences to a buffer store B1. When a predetermined number of sequences have been stored (seven in the specific example) words in corresponding positions in the sequences are read out in succession and pass through first and second registers 13 and 15 to permit comparison of successive words in unit 14. By this means the second system of run-length encoding is operated to produce a final signal which passes to a buffer store B2, which may be a magnetic tape or disc store, or is transmitted. The original serial binary data is examined by the first run-length encoder in terms of eight-bit sections which are passed into a shift register. If a change occurs in the bit state within a section (i.e. in terms of the picture there is a blackwhite or white-black transition), the binary data is transferred in parallel from the register to buffer B1 as a detail word. However, if no change occurs, the contents of the register are not transferred but an eight-stage counter is advanced one in count. This procedure continues for subsequent sections without a change so that the count state indicates the run length. When next a change occurs, or at the end of a scan line, the counter output in the form of an eight bit parallel word is transferred to buffer B1 as a compressed word. Each eight-bit word entered in the buffer is also expanded by three further tag bits. The first comprises a " 1 " bit for the word which starts a line scan sequence. This bit is employed only for control operation within the apparatus and may be dispensed with if the start of a sequence may be deduced from the word position in the buffer. The second bit comprises a " 1 " bit to denote a compression word and a " 0 " bit to denote a detail word, whilst the third comprises a " 1 " bit to denote white and a " 0 " bit to denote black for the run length conveyed by a compressed word. The operation is illustrated in Fig. 7 where 7a shows original binary picture data and 7b shows the words stored in buffer B1 with each sequence occupying a separate horizontal row. Section F1 of line 1 scan contains a bit change and is entered directly in row 1 as a detail word W1 preceded by tag bits " 100 " to denote line start and detail word. Likewise section F2 contains a change and is entered directly preceded by tag bit " 000." The remainder of the line F3 contains no change and is entered as a single word W3 denoting a run length of 255 sections (8 x 255 = 2040 bits) and preceded by tag bits " 011 " to denote a compressed word of white bits. In like manner the binary data from subsequent lines is entered as detail and compression words in rows 2, 3, 4 &c. Upon completion of the storage of seven sequences of words, the contents of the buffer are read out to the second run-length encoder. Read out is effected in columns so that successive words are taken from corresponding positions in the sequences. Thus the first column read out comprises the words W1, W(n + 1), W(n + 2) &c. which occupy the first positions in the sequences. Only the last ten bits of the words are used. The words are read in parallel through first and second registers 13, 15, Fig. 2, and compared in an " AND " gate unit 14. Where the words differ the contents of the second register are transferred to buffer B2 (or transmitted) ; where the words are identical a counter is advanced one in count. The counting procedure continues until a change occurs, whereupon the contents of the second register are again transferred to buffer B2 together with a three-bit word from the counter (so forming a 10 + 3 = 13 bit word) to denote the run length. Fig. 7c shows the operation where successive entries derived from a column of buffer B1 are shown in rows in buffer B2. Thus the first word W1 entered in row 1 corresponds to word W(n + 1) preceded by " 010 " denoting a run length of 2 since words W1 and W(n + 1) are identical. Words W<SP>1</SP>2 and W<SP>1</SP>3 correspond to words W(2n + 1) and W(3n + 1) preceded by " 000 " since successive words differ and the counter is not advanced. The transfer of column W2 into row 2 and successive columns into successive rows continues in like manner. The first run-length encoder is described in more detail with reference to Figs. 3 and 4 (not shown) and the second with reference to Fig. 5 (not shown).