Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2000-05-30
2002-06-11
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C341S050000, C711S109000
Reexamination Certificate
active
06404359
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a variable length code decoding system having a cache memory.
First, a modified Huffman code (simply called a “MH code” hereinafter) will be described briefly. A MH code system is to convert, in connection with a while/black binary image, the number of continuous pixels of the same color (white or black) (called a “run length”) into the MH code.
In the MH code, two series of codes are used which include a terminate code as shown in
FIG. 9 and a
makeup code as shown in
FIG. 10
, corresponding to the run length of the while or black. In this code, the run length is represented by a quotient and a remainder obtained when the run length is divided by 64. The makeup code corresponds to the quotient, and the remainder corresponds to the terminate code. Accordingly, assuming that the quotient is represented by M and the remainder is represented by T, the run length RL is expressed as follows:
RL=M×
64+
T
Therefore, the terminate code corresponds to the run length of “0” to “63”, and the makeup code corresponds to the run length which is a multiple of 64 and which reaches 2560 at maximum.
For example, in the case of a white/black binary image as shown in
FIG. 6
, first, three white pixels continues, and the run length becomes 3. Referring to the while run code of the run length “3” in the terminate code table of the MH code in
FIG. 9
, the code of “1000” can be obtained. Accordingly, the run length in the range of “0” pixel to 63 pixels can be coded by on the terminate code.
As regards the run length of not less than 64 pixels, the run length is coded by first using the makeup code table shown in FIG.
10
. The makeup code is followed by the terminate code indicating a difference between an actual run length and the run length represented by the makeup code (See the code corresponding to the run length of “WHITE 130” FIG.
6
.
Incidentally, the coding of a line head is started with a while run. If an actual line head is a black run, the while run of the run length “0” is coded.
Next, the feature of the MH code will be described. The MH code is constituted by the format that is shown FIG.
7
. As shown in
FIG. 7
, the MH code comprises 13 bits at maximum. In the bit format shown in
FIG. 7
, a leftmost bit is the most significant bit, and a rightmost bit is the least significant bit. The MH code is composed of a high place bit region
71
consisting of 0 bit to 7 bits, a succeeding fixed region
72
consisting of 1 bit, and a low place bit region
73
consisting of 7 bits at maximum. The values in the high place bit region
71
are “0”, and there is possibility that the region
71
itself does not exist. Namely, the MH code has a code sequence in which the number of continuing “0”s before a first “1” appears is seven at maximum and the number of bits succeeding to the first “1” is also seven at maximum.
For example, when the three white pixels continue as shown in
FIG. 6
, it is coded to a four-bit MH code which does not include the region
71
and which the region
72
of “1” and the region
73
of “000”. When 130 white pixels continue as shown in
FIG. 6
, it is coded to an MH code having no region
71
and the region
72
of “1” and the region
73
of “0010”, which is followed by an MH code having the region
71
of only one “0”, the region
72
of “1” and the region
73
of “11” outputted in the named order. The MH code is transferred serially from the most significant bit in order.
Now, a conventional MH code decoding system will be described. The decoding of the MH code is to convert the serially transferred and inputted MH code into the run length. This conversion is conventionally carried out by referring to a decoding conversion table stored in a ROM (read only memory).
Since the MH code is 13 bits at maximum, the conventional MH code decoding system is configured to carry out the decode by supplying a 14-bit address obtained by adding one bit of a white/black information to the MH code, to an address of the decoding conversion ROM, and by obtaining information of 11 bits in total, including 6 bits of the run length, four bits of the code length, and one bit indicative of which of the terminate code and the makeup code it is.
For example, the MH code decoding system disclosed by Japanese Patent Application Post-examination Publication No. JP-B-02-002350, is configured to decode as follows in order to reduce the capacity of the ROM. This decoding system utilizes the feature in which, in the serially transferred and inputted MH code sequence, the number of continuing “0”s before the first “1” appears is seven at maximum and the number of bits succeeding to the first “1” is also seven at maximum. An address of 11 bits comprising 3 bits indicative of the number of continuing “0”s before the first “1” appears, 7 bits succeeding to the first “1”, and one bit indicative of a while/black information, is supplied as an address of the decoding conversion ROM. Information of 10 bits in total comprising 6 bits of the run length, 3 bits indicative of the number of the remaining bits in the actual code, succeeding to “1” detected after the continuing “0”s, and one bit indicative of the terminate code/makeup code information. Thus, the decoding is carried out.
However, when the code data is inputted at a constant rate such as 33.6 Kbps, if the code length is relatively long, a processing time can have a margin, but if the code length is relative short, unless the processing is carried out at a high speed, the processing cannot be completed before a next code is inputted. For this purpose, a decoded data processed once is stored in a cache memory which can be read out at a speed higher than the ROM, so that when the same code pattern is inputted, the decoded data can be read out from the cache memory, without reading from a low speed ROM.
Furthermore, Japanese Patent Application Pre-examination Publication No. JP-A-09-185548 proposes a method in which decoded data corresponding to a relatively short length requiring a high speed reference, is previously transferred to a cache memory, and the cache memory is locked, so as to avoid a cache missing.
Referring to
FIG. 4
, there is shown a block diagram illustrating one example of the conventional MH code decoding system. In
FIG. 4
, a code input shift register 1 is a 8-bit shift register for bit-serially receiving a MH code sequence, and is controlled to shift leftward by a shifter
7
. A zero counting circuit
3
counts the number of continuing “0”s (which is seven at maximum) before the first “1” appears in an input sequence of the shift register
1
. A white/black register
2
is a one-bit register for designating the color of a white or black in the image. Here, the content of the white/black register
2
is inverted when the value of a T/M bit of an output of a control circuit
11
explained hereinafter indicates “T”.
A zero count register
4
holds three bits of a count output of the zero counting circuit
3
. A ROM (read only memory)
5
previously stores a decoding conversion table. The ROM
5
receives, as an address input, 11 bits in total consisting of the three bits of the zero count register
4
, code bits of 7 bits succeeding to the “1” firstly appearing in the shift register
1
, and one bit of the white/black register
2
designating the color of the white or black in the image. The ROM
5
outputs 10 bits in total consisting of 6 bits indicative of the run length (RL) to be actually decoded, one bit indicative of the terminate code/makeup code (T/M) information, and three bits indicative of the number of the remaining bits in the actual code, succeeding to the “1” firstly appearing in the shift register
1
.
A cache memory
8
can be read and written at a high speed, and receives, as an input address, the three bits of the zero count register
4
and the one bit of the white/black register
2
. A comparing circuit
10
receives and compares the most significant 7 bits of the output of the shift register
1
and 7 bits of a tag value outputted
Jean-Pierre Peguy
NEC Corporation
Scully Scott Murphy & Presser
LandOfFree
Variable length decoding system having a mask circuit for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Variable length decoding system having a mask circuit for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable length decoding system having a mask circuit for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2892074