Coded data generation or conversion – Digital code to digital code converters
Reexamination Certificate
2001-10-25
2003-03-18
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
C057S060000, C057S065000, C057S067000
Reexamination Certificate
active
06535149
ABSTRACT:
TECHNICAL FIELD
This invention relates to a device for compressing/decompressing bit strings comprising control means having a first processing speed and suitable for associating bit strings of a source information with corresponding compression codes.
In particular, the present invention relates to an electronic device for equipment for transmitting and receiving facsimiles (fax machines).
BACKGROUND ART
It is known that equipment such as, for example, fax machines are suitable for compressing the information to be transmitted (source information) and for decompressing the compressed information received.
It is also known that in fax machines the information to be transmitted is compressed and the information received is decompressed in accordance with suitable standards, for instance the T.4 standard of the International Telecommunications Union (ITU-T).
For example, it is known that during transmission the fax machine reads the source information in the form of rows of bits having, for example, horizontal and vertical resolution of 200 dots by 25.4 mm and compresses the information, consisting of sequences of white dots (white run length) or black dots (black run length), in accordance with the above-mentioned standard T.4, associating with sequence of bits of the same sign a code word of length between 2 and 13 bits.
It is also known that the compression operations, which consist in associating with each sequence of bits of the same sign the corresponding code word and in appending the code words in such a way as to form blocks of information comprising an integral number of bytes, are executed by the fax machine by means of its central unit (CPU) and appropriate programs stored in the memory of the fax machine itself.
In particular it is known that the appending of the code words, is extremely demanding of the fax machine's CPU and consequently requires high processing times.
In fact, the appending operation requires the CPU to operate in its own internal registers manipulating, not an integral number of bytes, but the bits and one by one at that, since the “code words” are strings of bits of variable length. For example, in order to append a “code word” 13 bits long and another one 3 bits long the CPU of a fax machine will have to execute the following operations: load the first code word in a first register, load the second code word in a second register and copy the second code word bit by bit from the second register to the first.
It is therefore obvious to those acquainted with the sector art that, assuming that the CPU takes at least 3 clock beats for each elementary instruction, the simple appending of a code word of 3 bits to another one of 13 bits requires at least 5 elementary instructions of the CPU and therefore at least 15 clock beats.
From the above example, it emerges that in a fax machine the compression times and, in particular, those for appending the code words in such a way as to form blocks of bytes, are generally high and are very closely dependant on the clock and the power of the CPU used.
Naturally the same remarks about the limits of the known art can also be applied to the decompression operations which consist in identifying, “extracting” or “unpacking” the single code words from blocks of information received and in reconstructing the source information on the basis of the code words identified.
In short, it is obvious that the compression and decompression times, in a fax machine for example, are for the known art a bottle-neck which is difficult to negotiate and avoided by using particularly fast or special CPU's.
It is also known, from the U.S. Pat. No. 5,436,626, a variable length encoder, used in high speed data transmission, which associates bit strings of a source information with corresponding compression codes at a first processing speed, and which appends the compression codes in order to form blocks of compressed information at a second processing speed greater than the first processing speed. However the disclosure of the U.S. Pat. No. 5,436,626 is performed in broad terms and concerns essentially only the main and general features of this variable length encoder. In particular the latter is proposed merely for a wide and generic use in the high-speed data transmission field. Therefore such document is very far from entering into the details which allow this variable length encoder to be implemented and to be improved as efficiency in more specific and limited fields, as for example the data transmission in a facsimile machine.
DISCLOSURE OF THE INVENTION
The object of this invention is to untie, in particular in a fax machine, the operations of compression of the source information and/or decompression of the compressed information received from the characteristics of the CPU used and, at the same time, to improve the times of these operations by at least a factor of 10.
This technical problem is solved by the device for compressing/decompressing bit strings characterised by storing means, having a second processing speed greater than the first processing speed, connected to the control means and suitable for appending the compression codes one to another in order to form blocks of compressed information, whereby the blocks of compressed information are suitable for being manipulated as blocks by the control means.
According to another characteristic, the device implements a new method for compressing/decompressing bit strings characterised in that the functions of appending compression codes (compression) and extracting compression codes (decompression) are performed bit by bit at a processing speed much greater than that of the CPU used by the fax.
REFERENCES:
patent: 4646061 (1987-02-01), Bledsoe
patent: 4700175 (1987-10-01), Bledsoe
patent: 4899147 (1990-02-01), Schiavo et al.
patent: 5321398 (1994-06-01), Ikeda
patent: 5389922 (1995-02-01), Seroussi et al.
patent: 5436626 (1995-07-01), Fujiwara et al.
patent: 5625356 (1997-04-01), Lee et al.
patent: 5717393 (1998-02-01), Nakano et al.
patent: 5808570 (1998-09-01), Bakhmutsky
patent: 5821886 (1998-10-01), Son
patent: 6157326 (2000-12-01), Van Der Vleuten et al.
Hao-Chieh Chang, et al.: “A VLSI architecture design of VLC encoder for high data rate vide/image coding” ISCAS'99. Proceedings of the 1999 IEEE International Synposium on Circuits and Systems VLSI (Cat. No. 99CH36349), ISCAS'99. Proceedings of the 1999 IEEE International Symposium on Circuits and Systems, VLSI, Orlando, FL, USA May 30-Jun. 2, 1999, p. 398-401 vol. 4, XP002145588 1999, Piscataway, NJ USA, IEEE, USA.
Shaw-Min Lei, et al.: “An Entropy Coding System for Digital HDTV Applications” IEEE Transactions on Circuits and Systems for Video Technology, US, IEEE Inc. New York, vol. 1, No. 1, Mar. 1, 1991, pp. 147-155.
Kovac, M., et al: “JAGUAR: A Fully Pipelined VLSI Architecture for JPEG Image Compression Standard”, Proceedings of the IEEE, US, IEEE, New York, vol. 83, No. 2, Feb. 1, 1995, pp. 247-257, XP000501243.
Bianco Gianpiero
Cerutti Walter
Banner & Witcoff , Ltd.
Mai Lam T.
Olivetti Tecnost S.p.A.
Tokar Michael
LandOfFree
Device for compressing/decompressing bit strings does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device for compressing/decompressing bit strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device for compressing/decompressing bit strings will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3041661