US 5,196,945 AGrant
Data Compression/Expansion Circuit for Facsimile Apparatus
Issue Date:1993-03-23
•8 Claims
•52 Drawing Sheets
Abstract
A facsimile unit including apparatus for simultaneously detecting color changes in image data being encoded and counting the number of pels between the color changes. The unit also includes a decoder having a binary tree embodied in ROMs for fast decoding of received signals.
Metadata
Assignee
- Motorola, Inc.
Inventors
- Steve Ho
- Patrick Law
Application Information
Application Number:US 5768276
Filing Date:1990-09-04
Priority Date:1990-09-04
Art Unit:262
Classifications
IPC:
H04N 141
Field of Search:
358426;427;430;261.1;261.2
Patent Drawings (52 sheets)
Description
The present invention pertains to data compression/expansion circuitry for facsimile apparatus and more particularly to data compression/expansion which is hardware oriented, rather than being incorporated almost entirely in software, and which may be integrated into a single chip.
Background of the Invention
It is of course well known to those skilled in the art of facsimile apparatus that all transmissions are standardized so that facsimile machines around the world can communicate with each other. It is necessary for all facsimile machines to convert information which is to be sent, into standard coded information which can be decoded by the proper facsimile machine when it is received.
The CCITT, which is an international telecommunications group, has set the standards for the various facsimile apparatus groups. At present, group 3 (G3) is the most important group since most facsimile apparatus falls within this group. Group 3 includes modified Huffman (MH) coding and modified Read (MR) coding.
In prior art facsimile machines, the compression or coding is accomplished by following a software procedure in a relatively standard, dedicated CPU, or microprocessor. The expansion or decoding is accomplished by following a substantially reverse software procedure in the same CPU or microprocessor.
The major problem with the prior art software procedures is that they are extremely complicated to write and difficult to incorporate into CPUs or microprocessors. Also, the software procedures can only perform one step at a time instead of allowing several related steps to occur simultaneously. Thus, the clock frequencies of the software processes must be very high to get the desired speed. Also, a dedicated CPU is used so that the actual hardware becomes relatively expensive.
Summary of the Invention
It is an object of the present invention to provide a new and improved data compression/expansion circuit for facsimile transmissions that is cheaper and simpler to manufacture.
It is a further object of the present invention to provide new and improved hardware oriented data compression/expansion circuitry for facsimile transmissions that will operate at least as fast as the prior software oriented facsimile transmission systems
It is a further object of the present invention to provide a new and improved data compression/expansion circuit for facsimile transmissions which can easily be integrated into a single semiconductor chip and which will operate on all G3 transmissions.
These and other objects are realized in.a data compression/expansion unit including a control register for selecting a specific coding scheme from a plurality of possible coding schemes including all G3 and at least some G4, an algorithmic state machine (ASM) for controlling the sequence and timing of the operations of the other components in accordance with the selected coding scheme, a picture element (pel) change detector for detecting color changes, run length registers controlled by the color change detections, an encoder for coding run length data into standard facsimile code, a decoder embodying a binary tree for decoding received data, and a buffer for arranging output bits of coded information into predetermined bytes. A vertical mode indicator is also included to provide an output indicative of the particular vertical mode of operation when the unit is operating in the MR or MMR modes.
Brief Description of the Drawings
Referring to the drawings, wherein like characters indicate like parts throughout the figures:
FIG. 1 is a simplified block diagram indicating the general flow of information between the various components;
FIG. 2-1 and 2-2 are block/schematic diagrams, illustrating the components and electrical connections therebetween in integrated circuit form, of a data compression/expansion unit embodying the present invention;
FIG. 3 is a schematic diagram of a control register included in the unit of FIG. 2;
FIG. 4-1, 4-2, 4-3 and 4-4 are schematic diagrams of an ASM included in the unit of FIG. 2;
FIG. 5 is a schematic diagram of a loop counter included in the unit of FIG. 2;
FIG. 6 is a schematic diagram of an MH block indicator included in the unit of FIG. 2;
FIG. 7-1 and 7-2 are schematic diagrams of pel change detect registers included in the unit of FIG. 2;
FIGS. 7A through 7g illustrate portions of FIG. 7 in more detail;
FIG. 8 is a schematic diagram of run length registers included in the unit of FIG. 2;
FIG. 9 is a schematic diagram of an encoder included in the unit of FIG. 2;
FIGS. 9A through 9C illustrate portions of FIG. 9 in more detail;
FIG. 10 is a schematic diagram of an output buffer included in the unit of FIG. 2;
FIGS. 10A through 10F illustrate portions of FIG. 10 in more detail;
FIG. 11-1, 11-2 and 11-3 are schematic diagrams of a decoder included in the unit of FIG. 2;
FIGS. 11A through 11L illustrate portions of FIG. 11 in more detail;
FIG. 12-1, 12-2 and 12-3 are schematic diagrams of a vertical mode indicator (VMI) included in the unit of FIG. 2;
FIGS. 13A and B are tables of CCITT standard codes; and
FIGS. 14-1, 14-2, 15-1 and 15-2 are tables of information stored in the decoder of FIG. 11.
Description of the Preferred Embodiment
Referring to FIGS. 1 and 2, a specific data compression/expansion unit 10 is illustrated which embodies the present invention. FIG. 1 is a simplified block diagram which illustrates the general flow of information and signals between the various components of unit 10. FIG. 2 illustrates the actual connections in an integrated circuit form.
In general, a control register 12 is used to select a specific coding scheme from the various G3 coding schemes or at least some of the known G4 coding schemes. An algorithmic state machine (ASM) 14 is loaded with a microcode which is used to control the other components of unit 10 in accordance with the specific coding scheme selected. Pel change detect registers (PCDR) 16 are used to detect color (black and white) changes between pels and control run length registers 18, which count the number of pels between pel changes. The run lengths are supplied to an encoder 20, which encodes them in accordance with the accepted CCITT standards. The encoded signals and coded data are supplied to an output buffer 22, which arranges the digital output signals into bytes of information that are acceptable to the data bus of unit 10.
A decoder 24 is included in unit 10 and is connected to receive transmitted data on the data bus and convert it back into pels. Unit 10 also includes a vertical mode indicator (VMI) 26 for operation in the MR or MMR code schemes. FIG. 2 also illustrates a loop counter 28 for operation with ASM 14 and an indicator 30 for indicating blocks of information in the MH block coding scheme.
The various schematic diagrams illustrating the specific components will now be discussed in the detail required for a complete understanding of the present invention. It should of course be understood that the specific embodiment disclosed herein is divided into components represented by individual circuits for ease of understanding and illustration. Unit 10 is designed to be incorporated into a single integrated circuit and, as such, might be somewhat different in appearance and/or layout.
Referring specifically to FIG. 3, control register 12 is illustrated schematically. Control register 12 includes an eight flip-flop register 32, which provides the desired control signals on one or more of six output lines in response to selection signals on the eight line data. The control signals are supplied as timing signals to all other components of unit 10 and the specific control signals utilized depends upon the selected coding scheme. A buffer 34, which is used in conjunction with bus oriented systems, is used to supply the control signals on the six output lines to the data bus. Since the operation of this circuit is straightforward, no further detailed explanation is required.
Referring specifically to FIG. 4, a schematic diagram of ASM 14 is illustrated. The microprogramme that controls the operation of the other components of unit 10 is written and stored in ASM 14. In this specific embodiment the microprogramme consists of a micro-code having a seven bit micro-address field; one bit is used to select either the jump or the next address and five bits are used to select the kind of input signal that should be compared, which comparison result is used to determine either the jump address or the next address that should be used for the next micro address. The rest of the micro-code consists of output command signals for the control of each individual block. Totally, there are nineteen command signals. ASM 14 receives start signals from control register 12. Coding is performed on a line to line basis so that ASM 14 should receive a start (restart) signal after each line is coded.
Since the components and operation of ASM 14 is straightforward and should be clear to those skilled in the art, no additional description on a part by part basis is deemed to be necessary. Further, loop counter 28, which is illustrated schematically in FIG. 5, includes a four stage ripple counter 36 that simply supplies command counting signals to ASM 14, in this embodiment only the LOOP=6 output is utilized. Also, the indicator circuit of FIG. 6 is utilized to provide an output for MH block operation.
FIG. 7 is a schematic diagram of pel change detect registers (PCDR) 16. PCDR 16 include a line width register 38, illustrated schematically in FIG. 7A, a controller 40, illustrated schematically in FIG. 7B, and five pel change detect registers 42 through 46, illustrated schematically in FIGS. 7C through 7G, respectively. Line width register 38 keeps a continual count of the image data being shifted through PCDR 16 and provides a last byte signal to controller 40, as well as a last bit signal output by way of a flip-flop 48. Registers 42 and 43 are used in the MH encoding mode to look for color changes. After every shift of registers 42 and 43 the image data is checked for a color change. Each time a color change occurs a signal is supplied to ASM 14. As previously stated, coding is performed on a line to line basis so that a single line is shifted through registers 42 and 43, after which ASM 14 starts the entire procedure again.
In the MR/MMR encoding modes a reference line of data is entered into registers 42 and 43 while the image data line to be coded is entered into registers 44, 45 and 46. Controller 40 controls registers 42 through 46 so that a complete reference data line and a complete image data line is shifted through the registers simultaneously. Color changes in both lines are compared and signals indicating the comparison are sent to VMI 26 and ASM 14.
FIG. 8 is a schematic diagram of run length register 18, which simply includes three, four stage ripple counters 50, 51 and 52 connected in series, to provide the capability of counting an entire line in several different modes of operation (e.g. 1728 bit lines, 2560 bit lines, etc.). Run length register 18 receives clock signals, each of which is representative of a byte of image data, and begins counting the image data at the beginning of a line or after each color change. Run length register 18 stops counting at the occurrence of each color change (sensed by PCDR 16), in response to commands from ASM 14. A run length signal, indicative of the number of bytes of image data between adjacent color changes, is supplied by register 18 to encoder 20.
In the MH mode of operation the run length signal is supplied directly to an encoder look-up table 54, illustrated schematically in FIG. 9B. Look-up table 54 includes three EROMs 55, 56 and 57. Look-up table 54 contains the standard CCITT transmission codes and it is partitioned into two sections for storing the different white run lengths and black run lengths, which code is illustrated in TABLE I (FIG. 13) for convenience. Each run length signal is utilized to address the specific stored code word representing that run length and color, which addressed code word is then supplied from look-up table 54 to buffer 22. As can be seen from TABLE I, the code words vary in length from two to thirteen bits and an eight bit, length indicating word is generated in look-up table 54 to accompany the code word when it is supplied to buffer 22.
It should be noted that the present apparatus has a substantial advantage over prior art facsimile apparatus wherein all steps are performed in a dedicated CPU utilizing software to control the operations. In such a system only one step can be performed at a time. For example, the software must include a first step directing the CPU to determine the next color change and, after the first step is completed, a second step would direct a run length measurement between the color changes. In the present apparatus these two steps are performed virtually simultaneously, i.e. PCDR 16 and run length register 18 are operating simultaneously. Similarly, many of the other described circuits reduce the total coding and decoding time by at least partially operating in overlapping modes.
Encoder 20 also includes an MR code generator 58, which is illustrated schematically in FIG. 9A. In the MR coding scheme, the first image data line is encoded using the MH coding scheme and subsequent image data lines are compared to the previous line. Thus, the MR scheme is a two dimensional scheme that simultaneously compares a reference line and an image data line. A code is then generated which is a mixture of MH coding and a description of the differences so that a duplicate of the reference line can be generated and changed to match the encoded line during decoding. The MR codes are specifically designed to let the decoder know that a MH or MR code is being sent. Thus, the decoder only needs to be controlled to operate in the MH or MR coding scheme.
The CCITT has carefully defined various differences, or modes, between the reference and data lines in the MR coding scheme. These include: seven vertical modes including V(0)--no changes, VL(1)--one change to the left, VL(2)--two changes to the left, VL(3)--three changes to the left, VR(1)--one change to the right, VR(2)--two changes to the right, and VR(3)--three changes to the right;.a pass mode wherein there is a color change on both ends of the reference line; and a horizontal mode wherein the color change differences between the data line and the reference line are greater than those specified above. The code words that represent these various modes are listed below:
At the end of each line, or the beginning of each new line, a special EOL code is generated so that a decoder can recognize the end of the line and prepare to receive a new line of image data. The EOL code is again dictated by the CCITT so that all facsimile apparatus can recognize it. In the present apparatus an EOL generator 60, illustrated schematically in FIG. 9C, is included in encoder 20. The EOL code is sent to buffer 22 with the other information from encoder 20.
Referring specifically to FIG. 10, output buffer 22 is illustrated schematically. It should be noted that the image data and the operation of unit 10, through encoder 20, are bit oriented so that output logic is used to generate an output in byte format. As an example, in the one dimensional MH coding scheme, code words representing all, or a portion, of a specific black or white run length vary from two to thirteen bits in length, as can be seen from TABLE I. However, the bus carrying data from encoder 20 to output buffer 22 is sixteen lines, for convenience. Buffer 22 can be controlled to arrange the data into eight or sixteen bit bytes. Therefore, when arranging the code words into bytes it is necessary to take empty lines into account. Output buffer 22 performs the function of receiving the encoded data from encoder 20, along with the eight bit length indicating words, and arranging the coded data into eight or sixteen bit bytes that can be sent out on the data bus.****
Output buffer 22 includes a block entitled "buf code" 61, which is illustrated in more detail in FIG. 10A. Referring to FIG. 10A, a parallel input/serial output shift register 62 which supplies bits to a serial input/parallel output shift register 64 is illustrated. The eight bit, length indicating word, which accompanies each code word generated in encoder 20, is used to preset a countdown register 66. The sixteen bits containing the code word are first loaded into shift register 62 and then clocked into shift register 64 as countdown register 66 begins counting. Output buffer 22 can be set to operate on eight or sixteen bit bytes. In the present description, eight bit bytes are explained for example only but it will be understood that operation in the sixteen bit mode is essentially similar. If countdown register 66 reaches zero before the output of shift register 64 becomes an eight bit byte, the next code word is shifted into register 62 and countdown register 66 is preset with the next accompanying length indicating word. If the output of shift register 64 becomes an eight bit byte before countdown register 66 reaches zero, any additional bits contained in the code word in shift register 62 will be included in the next eight bit byte. Output buffer 22 also includes an ASM 68, an indicator 70 and a buffer full register 72 to control the operation and timing of the flow of information.
Unit decoder 24 is illustrated schematically in FIG. 11 and primarily includes a decoder block 74. Decoder block 74 is illustrated in more detail in FIG. 11E, portions of which are also illustrated in more detail in FIGS. 11E1 and 11E2. Decoder block 74 includes a first ROM 76 and a second ROM 78 which embody a binary tree, the address/data arrangement of which is illustrated, in hexagonal code, in TABLE II and TABLE III of FIGS. 14 and 15, respectively. The data structure of the array in ROMs 76 and 78 is a mapping array developed in accordance with the expression M(i,j).fwdarw.k where the present state is i and the input of the binary code is j. The state machine of the decoder then changes the state to k, and the process is repeated.
TABLE I is separated into TABLE IA, which lists all terminating code words, and TABLE IB, which lists make up code words. A run length may be made up of one or more make-up code words from TABLE IB and must include a terminating code word from TABLE IA. The code word, or words, for a specific run length is supplied in parallel on the data bus to PCDR 16, which converts the data to serial form and supplies it to decoder block 74 on the pin DIN. The binary tree embodied in ROMs 76 and 78 includes terminal nodes, indicating a complete code word, and dummy nodes, indicating an error in the code word. Each terminal node contains the information of the run length or the mode of the respective code word. The dummy nodes, each of which contain all ones, indicate an error in the code or in the decode. The process stops only when the state transition hits a terminal node or one of the dummy nodes of the binary tree.
TABLE II and TABLE III are partitioned into four blocks. The first block, with addresses from 0000 to 006B, contains the state transition table for white run lengths and the second block, with addresses from 0080 to 00EB, contains the state transition table for black run lengths. The third block, with addresses from 0100 to 010E, is for MR two dimensional code decoding and the fourth block, with addresses from 0180 to 018B, is for the resynchronization of the end/beginning of the line (EOL). It should be noted that a few addresses having data designated as FF are placed between the blocks to insure separation.
Each zero (0) in the code word causes ROM 76 to output the next branch address of the binary tree and each one (1) in the code word causes ROM 78 to output the next branch address of the binary tree. A specific example will be useful in understanding the operation of the ROMs 76 and 78. Consider the next decode run length will be a white run. Further assume that the code word 1100, representing a run length of five white, is received and is serially applied to the input pin DIN of decoder block 74. The first bit (1) will be applied to ROM 78 and will address the data at address 0000, which is data 02. The second bit (1) will be applied to ROM 78 and will cause the output thereof to move from 02 to 06. This is accomplished by using the previous data (02) as an address for the second bit. The next bit (0) is applied to ROM 76, with the previous output (06) being used as an address, which produces an output from ROM 76 of 0D. The final bit (0) is applied to ROM 76 with 0D being used as an address, so that the terminal node 85 is reached. At this point ROM 76 provides a five white run length output to the data bus. This output is supplied to output buffer 22 where it is arranged, with other outputs from decoder 24, into bytes of image data that can be used by external apparatus for printing.
Block 84 of decoder 24 includes logic, controlled by the particular operating scheme of unit 10, for sensing the various modes (seven vertical, horizontal, etc.) in the data and producing signals representative of the various modes (on separate lines), which signals are used in unit 10 to produce the image data.
Many portions of unit 10 have not been described in detail, since the operation thereof is straightforward and well understood by those skilled in the art. However, a complete implementation of unit 10 is illustrated so that the construction and simplicity of operation can be understood by those skilled in the art.
Thus, new and improved data compression/expansion apparatus has been illustrated and described, which apparatus is much cheaper to construct than the prior art dedicated CPU structures and can be easily integrated on a single chip. Also, the present apparatus is faster than prior art software oriented apparatus because many tasks that require separate software steps are performed simultaneously in the hardware. Finally, the present apparatus is easily adaptable to any of the hardware (i.e. image readers, printers, etc.) presently on the market.
While we have shown and described a specific embodiment of the present invention, further modifications and improvements will occur to those skilled in the art. We desire it to be understood, therefore, that this invention is not limited to the particular form shown and we intend in the appended claims to cover all modifications which do not depart from the spirit and scope of this invention.
Claims
What we claim is:
1. A data compression/expansion unit for facsimile apparatus comprising: a control register for selecting a specific coding scheme to be utilized; an algorithmic state machine connected to said control register for receiving start signals therefrom and connected to other components of the unit for controlling the sequence and timing of the unit in accordance with the specific coding scheme selected in said control register; pel change detect registers coupled to receive image data from a data bus, said pel change detect registers shifting the image data therethrough to provide pel change output signals representing each color change in the image data; run length registers connected to provide run length output signals representative of the number of pels between each adjacent pair of pel change output signals, in response to the pel change output signals; said algorithmic state machine controlling said pel change detect registers and said run length registers to operate simultaneously to reduce the required run time; an encoder connected to receive the run length output signals and provide coded output signals, coded in accordance with the specific coding scheme selected in the control register; an output buffer connected to receive the coded output signals from said encoder and arrange them in bytes, each byte including a predetermined number of bits; and a decoder connected to said control register and algorithmic state machine and receiving binary code words on an input thereof, said decoder including at least one memory device having stored therein the nodes of a binary tree for converting the received binary code words into image data.
2. A data compression/expansion unit as claimed in claim 1 wherein the unit is integrated on a single semiconductor chip.
3. A data compression/expansion unit as claimed in claim 1 wherein the decoder has an output connected to the output buffer for arranging the image data into bytes of information.
4. A data compression/expansion unit as claimed in claim 3 wherein the unit further includes a data bus for the input and output of information, input image data being supplied to the pel change detect registers by the data bus and output image data being supplied by the output buffer on the data bus.
5. A data compression unit for facsimile apparatus comprising: a control register for selecting a specific coding scheme to be utilized; an algorithmic state machine connected to said control register for receiving start signals therefrom and connected to other components of the unit for controlling the sequence and timing of the unit in accordance with the specific coding scheme selected in said control register; pel change detect registers coupled to receive image data from a data bus, said pel change detect registers shifting the image data therethrough to provide pel change output signals representing each color change in the image data; run length registers connected to provide run length output signals representative of the number of pels between each adjacent pair of pel change output signals, in response to the pel change output signals; said algorithmic state machine controlling said pel change detect registers and said run length registers to operate simultaneously to reduce the required run time; an encoder connected to receive the run length output signals and provide coded output signals, coded in accordance with the specific coding scheme selected in the control register; and an output buffer connected to receive the coded output signals from said encoder and arrange them in bytes, each byte including a predetermined number of bits.
6. A data compression unit as claimed in claim 5 wherein the encoder includes apparatus for generating a length indicating word associated with each coded output signal.
7. A data compression unit as claimed in claim 6 wherein the output buffer is connected to receive the length indicating words generated by the encoder and includes circuitry for utilizing the length indicating words to arrange the coded output signals into bytes.
8. A data compression unit as claimed in claim 5 wherein the unit is integrated on a single semiconductor chip.