Note: Descriptions are shown in the official language in which they were submitted.
1 156764
--1--
This invention is a circuit which can be added to a fixed word
length data handling system for compacting variable length data words
into a fixed word length format.
It is frequently desirable in computer systems used for data
transmission to pack variable length format. If this operation is accom-
plished using software, through the use of shifting and masking techniques,
the amount of computer time spent on this operation will seriously degrade
the overall system performance and is a significant factor in reducing the
speed with which the computer can transmit or receive information.
Patent 4,109,310, entitled "Field Addressing System", describes
a computer based system which uses microcode programming and specialized
hardware to enable the writing or reading of variable length data in a fixed
word length computer. The modes of operation in that patent and in the
instant invention are different in that the prior field addressing system
is capable of loading any variable sized word anywhere in memory while
the instant invention is limited to the serial compacting of variable length
words into a fixed word length format as they are received. However,
the referenced patent does indicate, in its discussion of the microcode
involved, the numerous steps required to shift and mask variable data words
into a fixed word format, and to save residues, if any, for inclusion in the
next shifting and masking step.
One method of reducing the amount of time required to trans-
mit digital information is to encode the raw data through the use of run
length coding. To use a numerical example, instead of transmitting thirty -
two consecutive bits, the system would transmit the binary number 100,000,
the binary number for 32. Thus, thirty-two bits of information may be
transmitted using a six bit word. Using run length encoding, a significant
compression of data is possible.
Various improvements have been made on the basic technique
of run length encoding. For instance, in Patent No. 3,560,639 entitled
Cascade Run Length ~ncoding Technique, the basic run length coding is
modified so that the run lengths most often encountered are assigned the
shortest codes. In this way, a further compression over the basic run length
coding compression is achievable. This referenced patent also describes
a circuit comprising counters and shift registers for encoding and de-
coding the raw data into and out from this code.
76~
--2--
A greater amount of data compression can be achieved through
the use of Huffman codes. The advantages of using Huffman codes are:
1) that the basic Huffman code may be modified to result in the
greatest amount of compression based on the characteristics of the
particular data being transmitted, and 2) that the codes may be transmitted
serially at the transmitting end of the system with no additional data to
indicate the boundaries between codes but are still uniquely decodable at the
receiving end. A corresponding disadvantage of Huffman code is that there
is no correlation between the number of bits in the raw data and the number
of bits in the Huffman code, Huffman codes of varying length being
arbitrarily assigned to data words. Therefore, shifting and counting circuits
such as those described in U. S. Patent No. 3,560,639 are not suitable for the
generation and interpretation of Huffman codes. What is required in high
speed data transmission links, therefore, is a circuit which can be used to
encode raw data into Huffman code form or to decode Huffman codes into
raw data at high speeds. A particularly useful variation of this circuit would
be one that could be added to a computer system which would be able to
compact Huffman code data or, more generally, any sequence of variable
length words into a fixed word length computer memory or equivalent, said
circuit operating at high speeds and simultaneously requiring very little
computer time to accomplish this function.
The data compactor circuit described herein has a variety of uses
and can be most easily explained in terms of its use in a computer controlled
facsimile system for the transmission of imaginal data. At the facsimile
transmitter an image will be scanned and digitized and the resultant raw
data will be run length encoded by any well known means. In this numerical
example we will assume that a complete scan line comprises 1,024 bits so
that each run length will be any number from 1 to 1,024. Further assume
that these run lengths must be translated into Huffman codes of from three
to twenty-three bits. Finally, these Huffman codes must be packed into
fixed length words of eight bits p er word for local storage prior to
transmission to the facsimile receiver.
To accomplish this function at high speed and with a minimum
amount of time required by the computer, a circuit comprising a read only
memory containing two thousand words, each twenty-four bits wide, is
1 ~5676~
\
--3--
required. This read only memory is programmed to contain all of the
required Huffman codes and delimiter bits. These PROMS are in the address
space of the processor memory so that, in this specific example, when the
memory is addressed the corresponding Huffman code of up to twenty-three
bits will be produced. In the general case, the output can be expanded to
any length. These twenty-four bits will be loaded in parallel into a twenty-
four bit shift register such that the valid Huffman code will be located in
the least significant bits of the twenty-four bit register and the remainder
of the twenty-four bit register will be loaded with leading 0's. To indic~te
to the remainder of the system the start of the valid Huffman code, a de-
limiting 1 bit is placed between the leading 0's and the valid Huffman code to
signify the beginning of the Huffman code word.
After the twenty-four bit shift register is loaded in parallel from
the read only memory, the bits are shifted serially to a delimiter circuit
which strips the leading 0's and the delimiter bit. Thereafter, as bits are
shifted out of the twenty-four bit shift register they are allowed to serially
load an eight bit shift register. Whenever the eight bit shift register is full,the resultant eight bit word may be shifted out in parallel to computer
memory or any other buffer storage for subsequent transmission. Whenever
the twenty-four bit shift register becomes empty, a new run length code
may be used to address the ROM to produce the next Huffman code which is
again loaded in parallel into the twenty-four bit shift register. In this way,
the entire process of formatting the Huffman codes, which vary in this
numerical example from three to twenty-three bits, into fixed length words
of eight bits is accomplished at high speed and with little overhead.
The same circuit may also be used for the decornpression of data.
In this case the Huffman code is used to generate a PROM address, and the
output of the PROM is a string of video bits.
For long run lengths, one PROM location may have to be add-
ressed repeatedly to generate the required number of video bits. As a
numerical example, if 100 bits are to be generated, a location containing 23
bits may be addressed four times and a location containing 8 bits then
addressed once. The processor software is used to control this process.
If the eight bit shift register output must be loaded into a
computer memory, an existing computer l/O port could be used for this
purpose.
7 ~ ,~
However, for higher speed applications, a direct memory
access (DMA) channel would be used.
The identical circuit, comprising a read only
memory, a twenty-four bit shift register, a delimiter for
stripping leading O's and delimiter bits, and an eight
bit shift register for outputting the fixed length word,
could also be used as a character generator. In this
application the read only memory could be used to store
an entire font where each alphanumeric character is
typically defined by a twenty by twenty-two bit matrix.
In this case eleven bits of information could be used
to specify the particular alphanumeric character and
the line of that character, the selected line of twenty-
two bits being loaded into a twenty-two bit shift
register in parallel. Thereafter, this information is
serially shifted into an eitht bit shift register, as
above, for temporary storage and for ultimate use as a
means for generating character images through the use
of any raster output scanning device. In either case,
by using a read only memory, a large shift register
for receiving the ROM contents in parallel and a
smaller shift register for collecting words of the
fixed length required for the particular computer,
variable length data may be compacted into fixed length
words for use in a fixed word length system. In both
cases the circuit components can be varied so that read
only memory output words and fixed length words of any
size may be accommodated.
It is thus an object of an aspect of this inven-
tion to provide a circuit for the high speed conversion
of fixed length words to variable length words and to
compact these variable lengths words into a fixed
length format.
Various aspects of the invention are as follows:
~,.. .
1 15~7~
-4a-
A circuit for compacting variable length data into
a fixed word length format characterized by: an m bit per
word memory for storing and outputting variable length
data words, said m bits comprising a variable length data
word, unused bits and an delimiter bit to mark the boundary
between said data word and said unused bits, an m bit shift
register adapted to receive the m bits of memory output in
parallel, an n bit shift register for serially receiving
the contents of said m bit shift register, logic for prevent-
ing the loading of said unused bits and said delimiter bitinto said n bit shift register as said bits are shifted out
of said m bit register, a counter responsive to the count
of bits remaining in said m bit shift register for enabling
said memory to load an m bit next word into said m bit
shift register after the previous m bit register contents
have been completely shifted out, and a counter responsive
to the count of bits loaded into said n bit register for
enabling said n bit register to OlltpUt its contents in
parallel after serially receiving n bits of data.
A method of converting input words selected at
random from a first list to the corresponding data words
on a second list, where the second list data words are of
variable length, and for compacting said variable length
data words into fixed output data words of n bits charac-
terized by the steps of: initially loading all variable
length data words into memory, and further loading a de-
limiter bit to mark the boundary between each variable
length data word and the unused bits of each memory loca-
tion, using an input word to construct an address with
which to address said memory, thereby accessing and out-
putting to a first shift register the corresponding
variable length word, shifting said variable length data
word to strip out the unused bits, shifting the remain-
ing bits which consitute the variable length data word
1 156764
-4b-
into a second shift register, outputting from said second
shift register the bits of each output word of compacted
data in parallel when said second shift register becomes
full, and using the next input data word to access and
output the next variable length data word from memory when
the previous variable length word has been completely shift-
ed out of said first register.
The method of converting a code word corresponding
to a variable run length of data bits into the actual run
length of data bits and for compacting said variable run
length of data bits into fixed length data word of n bits
where the run length is greater than n characterized by
the steps of: a) initially loading m locations of memory
with a number of data bits equal to the memory location
address, b) 1st determining the number n of bits in the
run length from the code word, c) 2nd determining the
quotient Q and remainder R by dividing n by m, d) access-
ing and outputting from memory the contents of location
m into a first shift register, e) shifting said first
shift register contents into a second shift register of
n bits, f) outputting from said second shift register the
bits of each output word of compacted data in parallel
when said second shift registèr becomes full, g) waiting
until said first shift register becomes empty, h) repeat-
ing steps d) through g) Q times, i) accessing and output-
ting from memory the contents of location R into said
first shift register, j) shifting said location R data
to strip out the unused bits, and k) repeating steps e)
and f).
In a facsimile transmitter, a circuit for convert-
ing run length code into variable length code and for
compacting said variable length code into n fixed length
words, characterized by, a memory in which variable length
codes, unused bits and delimiter bits are stored, said
memory arranged so that when an address which is a function
of a run length is received, the associated variable
1 ~5~7~.
length code will be produced, a first shift register adapt-
ed to receive the output bits from said memory in parallel,
logic for stripping said unused bits and delimiter bit
from said first register output, a second shift register
adapted to receive the variable length code bits serially
from said first shift register, a counter for enabling
said second shift register to output its contents in
parallel when said second shift register is full, and
processor for generating a next address for said memory
when said first shift register becomes empty.
Figure lA is a hypothetical set of deciman run
lengths and corresponding Huffman codes.
Figure lB shows the arrangement of these codes in
ROM.
Figures lC through lG show the process for compact-
ing these codes into 8 bit output words and remainders.
Figure 2A is a simplified schematic of the ROM and
24 bit shift register.
Figure 2B is a flow chart of a decompression sub-
routine for producing run lengths in excess of the memoryword length.
Figure 2C is a portion of PROM used in conjuction
with said subroutine of Figure 2B.
1 156764
Figure 3 shows the arrangement of ROM data when used as a font
generator.
Figure 4 is a block diagram of the system including CPU, main
memory, DMA channel and data compacting circuit.
Figure 5 is a schematic of the leading zero and delimiter bit
stripper.
The disclosed embodiment stores Huffman codes, of from three to
twenty-three bits in length, in a ROM comprising three devices, each with a
capacity of 1,024 words by eight bits. In fact, the codes in the preferred
embodiment are not pure Huffman codes but the differences are not significant
in relation to the apparatus and methods described herein. Assuming, for
purposes of discussion, that the Huffman equivalents of the decimal run lengths
9, 40 and l30 are shown in Figure lA, and are stored in ROM as shown in Figure
lB, then the circuit would operate functionally as follows:
The ROM would first be addressed by a relative address
corresponding to the Huffman code of the run length, resulting in twenty-four
bits being shifted in parallel into a shift register. Next, this word would be
shifted serially out to a delimiter circuit which would strip the leading 0's and
the delimiter bit. If the first word accessed were the Huffman code equivalent
of the decimal number 9, after stripping, the remainder would be 1011, as
shown. This would be shifted serially into the first five bits of an eight bit shift
register as shown in Figure lC.
The next number is then accessed from ROM. In this case we will
assume the decimal number 40. After stripping the binary number 1011011 will
be shifted into the 8 bit shift register. In this case, after the first three bits
are shifted in, the 8 bit shift register is full, and the word contained thereinmay be transferred out in parallel to buffer memory, as shown in Figure lD.
The remaining bits are then shifted into the 8 bit shift register,
resulting in the bit pattern of Fig. lE.
The third code word corresponding to the decimal number 130 is
next processed, the first 4 bits resulting in a second output word as in Fig. lFand a remainder as shown in Fig. lG. In this way, variable length words are
compacted into fixed word segments.
Fig. 2 is a block diagram of the address bus, ROM and twenty-four
1 1S67~
-- 6 --
bit shift register. An eleven bit address is received by ROM devices 15 in
parallel and a twenty-four bit parallel output is applied to the twenty-four bitshift register 14. The direction of shift can be either direction, in Fig. 2 thebits are shifted to the right in the 24 bit shift register 14. As shown, each word
5 consists of leading 0's, a delimiter 1 bit, and the pattern which could
compromise any combination of l's and 0's, here indicated with X's. The
contents of ROM 15 could be either a video pattern, as shown, to be used in a
character generator mode or could be Huffman codes or equivalent to be used
as described above.
In the event that a run length longer than 23 bits must be produced,
a 24 word section of PROM memory, as shown in Fig. 2C, and a processor
program, as shown in Fig. 2B, may be used in conjunction with this circuit.
First, the program divides the number of bits in the desired run length by the
maximum number of bits which can be contained in one PROM location. For a
15 numerical example, assume that the run length is 100 (N=100), and the
maximum number of bits per memory location is 23. Then the quotient will be
4 (Q=4) and the remainder will be 8 (R=8). The processor will then loop through
steps #4,#5 and #6 four times to produce 92 bits, and finally, fall through step#7 to add the last 8 bits. Using this decompression technique, run lengths in
20 excess of the memory word length may be produced.
The indicated addresses of the two accessed words in Fig. 2 are
4016 and 4017, octal. These would be typical addresses in a computer with a
2K main memory and where the 4XXX address block is reserved for this data
compaction circuit ROM.
Fig. 3 shows the typical contents of a ROM when the circuit is used
in its character generation mode. At the system level, the appropriate
character identifier and the raster scan line number are used as address
components. The addressed line of data is then loaded into the 24 bit shift
register as before.
For the letter "R", bit 21 is the delimiter bit, leaving 20 bits to be
output as character data. For a narrower letter, the delimiter bit could occupy
a position further to the left and the character centered in the remaining spaceto create variable width letter spacing. In this figure, all empty bit positionsshould be 0, but except for the first row, these bits were omitted for greater
35 clarity.
1 15676~
The overall block diagram of this system is shown in Figure 4. The
CPU 10 and memory 11 can be connected in any well known configuration.
Here the CPU 10 drives the address bus 12 and both CPU 10 and memory 11
communicate bidirectionally with the data bus 13. A discrete memory read line
24 is also provided to enable main rnemory 11 or ROM 15 read out.
When ROM 15 is addressed, twenty-four bits of data are loaded in
parallel into the twenty-four bit shift register 14. Next, under control of the
shift control logic 17, ~his twenty-four bit data word is shifted right until all
leading 0's and the delimiter bit are stripped. Then, the valid data bits are
serially shifted into the eight bit shift register 16.
Each clock pulse used to shift the twenty-four bit shift register 14
data is counted by the counter 20. When the twenty-four bit shift register is
empty, a "count complete" signal is coupled from the counter 20 to the shift
control logic 17 as shown, and also to the CPU 10. The CPU 10 will then
address another ROM data word to begin a new cycle.
Each clock pulse used to shift the eight bit shift register 16 is
counted by the counter 18. When the counter 18 is full, a "count complete"
signal is coupled from the counter 18 to the shift control logic 17, state control
logic 26, and latch 22 and the DMA request Flip Flop 21. As a result, the eight
bit shift register 16 data word is immediately latched into the eight bit latch
22, freeing the eight bit shift register 16 to begin compacting the next word.
The 8 bit data word in the latch can then wait for the DMA 27 to steal a
memory cycle during which the eight bit word will be loaded from latch 22 into
memory 11 through the bus driver 23 and the data bus 13.
During any memory read cycle, the memory read line 24 enables
both main memory 11 and ROM 15. However, the twenty-four bit shift register
14 will load the data presented to it only if a ROM address is specified by the
CPU 10. This decisiona is made by the address decode logic 24, the output of
which allows a load signal from the state control logic to pass through gate 25.The compacted data may be loaded into a buffer register or into a
CPU through any standard I/O port or DMA channel. In this described
embodiment, the loading is accomplished through the use of a direct memory
access circuit 27. When the DMA request flip flop 21 receives an indication
originating from the counter 18 that an 8 bit word is ready for storage, it issues
l 1S6764
-- 8 --
a channel request on line 28 to the DMA access circuit 27, which returns a
channel acknowledge signal on line 30, resetting the DMA request flip flop 21.
Simultaneously, the DMA 27 sends a hold request signal on line 31 to the CPU,
requesting the CPU 10 to release the memory 11 long enough for a load cycle.
5 When a hold acknowledge signal is received from the CPU 10 on line 36 by the
DMA 27, an I/O read command is issued on line 32 to the bus driver 23. A
memory write command is also issued to the memory 11 on line 33, thus
enabling the bus driver 23 to load one word from the latch 22 through the data
bus 13 into memory 11.
As an alternative, the I/O port could be used to load the memory.
In this case when the count complete signal is received by the CPU 10 on line
37, the CPU will transmit an l/O read signal on line 32 to enable the bus driver23 to drive the data bus. An ordinary memory read cycle will then load the
data into memory 11.
Fig. 5 is a schematic of a circuit for stripping leading 0's and the
delimiter bit. Bits are shifted out from the twenty-four bit shift register 14
but are blocked at the 8 bit shift register 16 because of a clock inhibiting signal
from flip flop 35 to gate 34. Following an initial string of leading 0's, a
delimiter 1 bit will set flip flop 35, enabling gate 34 and allowing the remaining
20 valid data bits to be loaded into the eight bit shift register 16. Finally, when
the twenty-four bit shift register 14 is empty, the counter 20 will reset the
twenty-four bit shift register 14 and the flip flop 35, to start a new cycle.
This circuit has been described in terms of using a ROM for storage
of fonts, data bit run lengths and Huffman codes. However, it is obvious that
25 volatile RAM may also be used. In this case, the coding may be changed to
increase efficiency when a different mode of operation is entered (half tone
images to text, for instance). Similarly, a change of font could be
accomplished by loading a different data set into the character generator. This
description is based on an example where the ROM word length is longer than
30 the fixed word length. This is not a necessary limitation, short variable words
may be compacted into longer fixed length words with this data compaction
circuit. Also, codes other than Huffman codes may be used in the compression
and decompression modes described herein.
