Variable-Length Codeword Encoder

This invention relates to an entropy encoder for use in a high speed data transmission system, and more particularly to a variable-length codeword encoder.

Variable-length coding is a coding technique often used for lossless data compression. In accordance with this technique, fixed-length data is converted into variable-length codewords according to the statistics of the data. In general, the lengths of the codewords are chosen so that shorter codewords are used to represent the more frequently occurring data and longer codewords are chosen to represent the less frequently occurring data. By properly assigning the variable-length codewords to the library of all possible source codewords, the average word length of the variable-length code is shorter than that of the original data and, therefore, data compression is achieved. Huffman code design is a procedure commonly used to construct a minimum redundant variable-length code for a known data statistic. Generally, the encoding process can be implemented by a table-lookup process using the input data to address the table. The codewords and word-lengths are stored as table contents. Each fixed-length input symbol word is coded, at a sample clock rate, into the variable-length codeword it is associated with in the table, and the associated table codeword lengths are used to control circuitry to bit-by-bit concatenate the successive variable-length codewords into a bit stream. The bit stream is then divided into fixed-length data segments and stored in a buffer and then outputted sequentially at either a fixed or a variable rate for transmission over a data channel. At the receiving end, a buffer generally stores the received bit stream in fixed-length segments and retrieves these segments to form a continuous stream from which each variable-length codeword is successively decoded, at the fixed sample clock rate, back into its original source symbol.

Both the encoding and decoding of variable-length codewords are difficult at high speeds. Generally, during each symbol period in both the encoder and decoder all the bits in a variable-length codeword may need to be shifted through a register at a rate substantially greater than the sample clock rate. Speed requirements are a particular critical concern in the digital transmission of high definition (HDTV) signals. In such an HDTV system the total sample rate (combining luminance and chrominance signals) is likely to be 100 MHz. If variable-length coding is used, the maximum length codeword could typically be 16 bits. In the worst case, therefore, an encoder or decoder would need to shift bits through a register at 16 times the sample rate, or at 1.6 G bits/sec, to code or decode words at the sample rate. Such high speeds are very difficult to implement using current IC technology.

The problem of high-speed decoding in a variable-length decoder is approached in co-pending patent application, Ser. No. 546,415, filed Jun. 29, 1990, co-invented by two of the co-inventors herein. That decoder includes two cascaded latch circuits, each having a bit capacity equal to the maximum codeword length and which store consecutive bits supplied from an input buffer memory which stores the stream to be decoded in fixed-length data segments; a barrel shifter, which is input from the two latch circuits and which provides a sliding decoding window output equal in length to the maximum codeword length; an accumulator which accumulates, modulo the maximum codeword length, the lengths of the sequentially decoded variable-length codewords; and a table-lookup memory device, which outputs, for an input sequence of bits that begins with the first bit of a variable-length codeword, a fixed-length word corresponding to that variable-length codeword and that variable-length codeword length. As a codeword is decoded during each clock cycle, its length is accumulated and the decoding window of the barrel shifter is directly shifted to begin with the first bit of the next to-be-decoded codeword. When, during a clock cycle, the accumulated lengths exceeds the maximum codeword length, which indicates that all the bits in the first latch circuit have been decoded, the bits in the second latch are transferred into the first latch and the next fixed-length data-segment of bits is read into the second latch from the buffer memory. With this decoder, a continuous stream of bits from the buffer is always at-the-ready to be decoded and the variable-length codewords can be decoded at the sample clock rate without the necessity of clocking bits at a very high bit rate.

As aforenoted, at the transmitting end of a high-speed data transmission system, a similar problem needs to be solved in order to code each symbol at the sample clock rate without needing to shift bits at a higher rate. Although at a high level of understanding, the problem of coding and decoding are conceptually related, in actuality the problems associated with the coding and decoding of variable-length codewords are dissimilar. Whereas the problem in the decoder is to determine, from an already existing continuous stream of variable-length words, the end of each successive word and then shift to the next word in a single clock cycle, the encoder oppositely must form the continuous stream from successive words that arrive a constant rate but with a variable number of bits. Thus, the encoder must concatenate each successive word with a previous one in a single clock cycle. Furthermore, the concatenated stream needs to be divided into fixed-length segments to be stored in a buffer for later accessing for transmission over the data channel at either a fixed or variable bit rate.

An object of the present invention is to code input symbols into variable-length codewords at a sample clock rate, to concatenate, at each clock cycle, the resultant variable-length codewords into a stream, and to output to a buffer fixed-length segments of the concatenated stream as that fixed number of bits are accumulated.

The variable-length encoder of the present invention includes a memory device for producing, in response to each symbol to be encoded, a variable-length codeword and a codeword length that indicates the length of each codeword. At each clock cycle, the variable-length codeword is concatenated in a bit stream with previously concatenated variable-length codeword bits. When a predetermined number of bits have been accumulated in the stream, a segment of that predetermined number of bits are output. The encoder includes an accumulator which accumulates, modulo-(the predetermined number of bits in the segment), the lengths of successive variable-length codewords being encoded. At each clock cycle a variable-length codeword, having a predetermined maximum codeword length, is input to a shift control circuit, which outputs its input codeword in an output window having a bit-width equal to the sum of the maximum codeword length and the predetermined number of bits in the segment. The input codeword is shifted in the output window from the most significant bit position in the window by a shift value determined from the accumulated previous codeword lengths. The shifted input codeword at the output of the shift control circuit is combined with accumulated previous variable-length codeword bits to form a new concatenated stream of bits which are stored, in two consecutive portions, in first and second storage devices which hold the predetermined segment length number of bits and the maximum codeword length number of bits, respectively. At the next clock cycle, this stream of bits in the first and second storage devices is concatenated with the next shifted variable-length codeword to form the new stream, which is then stored. The cycle continues until the accumulator indicates that the predetermined segment number of bits has been accumulated. At that time, those bits in the first storage device are outputted, and the bits in the second storage device are shifted to the more significant bit positions in the stream. At the next clock cycle, the remaining bits in the stream are concatenated with the next shifted variable-length codeword to form a new stream which is then stored in the first and second storage devices. The shift-concatenate-store cycle is repeated until the predetermined segment number of bits are again accumulated. As before, those segment bits are outputted and the remaining bits shifted to the more significant bit positions in the stream.

FIG. 1 is a block diagram of a variable-length encoder of the present invention which encodes input words into variable-length words, concatenates successive variable-length codewords, and stores fixed-length segments of the concatenated variable-length words in a buffer for transmission over a channel;

FIG. 2 is a block diagram of the data generation circuit and the buffer of the encoder in FIG. 1, which concatenates the successive variable-length codewords and produces fixed-length output segments as input to the buffer as that fixed number of bits are accumulated;

FIG. 3 illustrates the operation of the cross bar shift control circuit within the data generation circuit of FIG. 2;

FIG. 4 is a table showing the output of the cross bar shift control circuit for each possible input shift value; and

FIGS. 5A and 5B, when placed side-by-side as shown in FIG. 5C, illustrate an example of the operation of the data generation circuit in FIG. 2 through several clock cycles.

With reference to FIG. 1, input symbols in a fixed-length word format are input over lead 11 to an input register 12 in response to a clock signal 13 at the sample clock rate. In the example to be described herein it will be assumed for purposes of illustration that each fixed-length word consists of 8-bits, and is to be coded into a variable-length codeword that ranges between 2- and 8-bits long. The variable-length codeword library is formulated depending upon the a priori data statistics for each input symbol so that the more likely symbols are assigned to the shorter variable-length codewords and the less likely input symbols are assigned to the longer variable-length codewords. In an actual system a variable-length codeword would more likely be between 2- and 16-bits long. In order, however, to simplify the discussion that follows and the example of FIGS. 5A and 5B, the maximum length of each variable-length word has been limited to 8-bits.

Input register 12 outputs on parallel leads 14, at the clock rate, successive fixed-length input words to be encoded. Each successive fixed-length input word is simultaneously applied to a variable-length codeword table 15 and a codeword length table 16. Tables 15 and 16 are table-lookup memory devices which have stored, for each possible fixed-length input codeword, the associated variable-length codeword and the associated variable-length codeword length, respectively. The output of variable-length codeword table 15 is thus a variable-length word having between 2- and 8-bits. Since a table-lookup memory device can only produce a fixed-length output, the output of table 15 on the eight parallel leads 17 consists of the codeword bits (between 2- and 8-bits) in the upper more significant bit locations, followed a necessary number of "0" filler bits in the lower less significant non-codeword bit positions. The output of codeword length table 16, on parallel leads 18, indicates, in binary fashion, the length of each variable-length codeword being output by table 15 on leads 17. Since the length of each variable-length codeword is between 2-and 8-bits, the output of codeword length table 16 is represented on three parallel output leads 18. Although shown in FIG. 1 as two separate memory devices, tables 15 and 16 could be combined in a single device, such as a programmable logic array, having an input plane and two output planes, and which produces two separate outputs for each input codeword.

The variable-length codeword output of table 15 and the codeword length output of table 16 are input to data generation circuit 20. As will be described in detail hereinafter, data generation circuit 20 concatenates, at the clock rate of the clock signal 13, the significant non-filler codeword bits of the current variable-length codeword on leads 17 with the bits from previous word or words. When 8-bits worth of concatenated codeword bits have been accumulated, data generation circuit 20 outputs these 8-bits on parallel leads 21 and, in response to a signal on lead 22, inputs this 8-bit data segment into buffer 23. The successively stored 8-bit data segments are output in a time-ordered fashion onto transmission channel 24 at either a fixed-rate or a variable-rate, depending upon the particular transmission system requirements. In the particular embodiment being described, each output segment has been assumed to be 8-bits. In an actual system each output segment can be any length greater than or equal to the maximum-length variable-length codeword.

Data generation circuit 20 will be described with reference to FIG. 2. Similar numerical designations have been given to corresponding elements in FIGS. 1 and 2. Each variable-length codeword output by table 15 on leads 17, at the clock rate, is input to cross bar shift control circuit 30, and each corresponding codeword length output by table 16 on leads 18 is input to adder 31. The output of adder 31, on parallel leads 32, is input to an adder latch 33, the output of which, on parallel leads 34, forms a second input to adder 31. Adder 31 in cooperation with adder latch 33, forms an accumulator which accumulates, modulo-8, the codeword lengths of successive codewords. Specifically, at each clock tick of clock signal 13, the sum of the previous accumulated codeword lengths on leads 34, and the current codeword length on leads 18, is entered into latch 33. Adder 31 generates a "carry" signal on lead 35 at any clock tick at which the sum of the current codeword length plus the previously accumulated codeword lengths is equal to or greater than eight. The carry signal is input to a carry latch 36. At the clock tick following a carry signal of "1", carry latch produces a carry latch signal of "1" on lead 37. As will be described, this carry latch signal, which is "1" when more than eight codeword bits have been accumulated, initiates the output of an 8-bit segment of concatenated codeword bits.

The concatenated codeword bit stream is produced by the cooperation of cross bar shift control circuit 30, and OR circuit 38. Cross bar shift control circuit 30 is controlled by a 3-bit shift value, consisting of bits S.sub.2 -S.sub.0 on output leads 34 of adder latch 33. Cross bar shift control circuit 30 is best described with reference to FIGS. 3 and 4. Cross bar shift control circuit 30 has an 8-bit input window on leads 17, and a 16-bit output window on leads 40. The variable-length codeword input on leads 17 consists of 8-bits, X.sub.7 -X.sub.0. Depending upon the codeword length, between zero and six of the less significant bits of this input sequence are "0"s. In response to the shift value, S.sub.2 -S.sub.0, on leads 34, cross bar shift control circuit shifts its input sequence within the 16-bit output window consisting of Y.sub.15 -Y.sub.0. Thus, for a shift value of five, or "101", the input bits X.sub.7 -X.sub.0, are shifted 5-bits. As noted in FIG. 7, therefore, five "0" bits are inserted before X.sub.7 -X.sub.0, and three "0" bits are inserted as low-order bits. FIG. 8 shows the eight output sequences for the eight possible shift values, S0-S7.

The 16-bit output 40 of cross bar shift control circuit 30 is input to OR circuit 38, together with the combined 8-bit output of data selector 41 and the 8-bit output of data selector 42 on the 16 parallel leads 45. As will be described, the 8-bit output of data selector 41 contains up to 7-bits of previous concatenated variable-length codeword bits and the 8-bit output of data selector 42 is always all "0"s. At noted hereinabove, and as will be more evident in the operational example that will be described later, the shift value input to cross bar shift control circuit 30 is equal to that number of accumulated bits. The output of cross bar shift control circuit 30 is thus shifted so that same number of "0" bits are inserted before the current variable-length codeword on leads 17. OR circuit 38 is thus able to concatenate the current variable-length codeword with the previous concatenated variable-length bits that have not yet been output as an 8-bit segment, to form a 16-bit sequence of concatenated bits. This 16-bit sequence includes up to 7-bits of previous codeword bits and up to the 8-bit longest-length variable-length word of the current codeword. The significant number of codeword bits in this sequence is thus equal to the sum of previous accumulated modulo-8 codeword lengths plus the codeword length of the current codeword.

The 16-bit sequence at the output of OR circuit 38 consists of eight upper more significant bit outputs on leads 51, and eight lower less significant bit outputs on leads 52. At the clock tick that follows the OR combination, the upper 8-bits are stored in upper latch 53 and the lower 8-bits are stored in lower latch 54. The upper latch 53 is connected to one set of inputs of data selector 41 and the lower latch is connected to a second set of inputs of data selector 41 as well as a first set of inputs of data selector 42. Eight parallel "0"s are connected via leads 55 as a second set of inputs to data selector 42.

Data selectors 41 and 42 are controlled by the carry latch signal on lead 37. When the carry latch is "0", which indicates that fewer than eight previous variable-length codeword bits have been accumulated, data selectors 41 and 42 select their first inputs as outputs. The 16-bits on leads 45 from the combined outputs of data selectors 41 and 42 thus form the input to OR circuit for concatenation with the next variable-length codeword, the latter being shifted by cross bar shift control circuit 30 by that same accumulated number of bits. When carry latch is "1", however, indicating that at least 8-bits have been accumulated, data selectors 41 and 42 select their second inputs as outputs. In this latter case, therefore, the contents of the lower latch are transferred into the most significant bit positions of the 16-bit input to OR circuit 38 and the eight least significant bit positions are set to "0". Since the accumulator is counting modulo-8, the shift value input to cross bar shift control circuit 30 is automatically set to shift the next input variable-length codeword by the number of codeword bits still remaining in the combined outputs of data selectors 41 and 42. The operation of these circuits thus always cooperate to ensure that each successive variable-length codeword on leads 17 is concatenated with the previous concatenated codeword bits.

Each time 8-bits are accumulated, the resultant 8-bit segment of concatenated variable-length codeword bits are ready to be stored in the buffer. Upper latch 53 is thus also connected via leads 56 to output register 57. Output register 57 is controlled by carry latch signal on lead 37. When the carry latch signal is "1" output register 57 stores the current 8-bits in upper latch 53. Thus, at the clock tick following an accumulation of 8-bits, eight of the concatenated bits then in upper latch 53 form a new segment and the remaining bits then in the lower latch 54 become the more significant bits for the next successive concatenation.

Output register 57 stores the most recent segment of concatenated variable-length codewords bits until the clock tick that follows a carry latch signal of "1", when it is updated with the next 8-bit segment. Output register 57 is connected to the buffer 23 via leads 21. Input of each successive 8-bit segment to buffer 23 is controlled by buffer latch 58 via lead 22. Only when the buffer latch 58 is "1", is the current segment in output register 57 input to the buffer 23. Buffer latch 58 is connected to carry latch 36 and to the clock signal 13. Buffer latch 58 is thus "1" at the clock tick that follows a carry latch of "1". Only at that time, therefore, is the segment in output register 57 stored in the buffer 23. An 8-bit segment is thus input to the buffer 23 only for each new 8-bit segment of concatenated codeword bits.

Operation of the data generation circuit 20 in FIG. 2 is more readily understood with reference to the example shown in the table formed by the combination of FIGS. 5A and 5B, placed side-by-side, as shown in FIG. 5C. The left hand "clock" entry in FIG. 5A has been duplicated in FIG. 5B for ease of reading. FIGS. 5A and 5B will hereinafter be referred to as FIG. 5, singularly. FIG. 5 will be described in conjunction with FIG. 2.

Adder latch 33 and carry latch 36 are initially set with 0 as indicated in FIG. 5 with a box surrounding the numeral. The upper latch 53 and the lower latch 54 are also initially set with all 0s in each bit position, as indicated with boxes. The initial variable-length codeword on leads 17 is a.sub.1 a.sub.2 a.sub.3 00000 and the corresponding codeword length, on leads 18, is equivalent to a length of 3. At the first clock tick output register 57 contains noise, indicated by an X in the table. The output of adder 31 is 3, and carry is 0. The output 40 of cross bar shift control circuit 30 is determined by the input variable-length codeword, as shifted by the shift value of adder latch 33, which is initially set at 0. The 16-bit cross bar output is thus a.sub.1 a.sub.2 a.sub.3 0000000000000. The outputs of data selectors 41 and 42 are determined by the initial sequences in upper and lower latches 53 and 54 and are therefore each 00000000. The 16-bit output of OR circuit 38 is the combination of the output of cross bar shift control circuit 30 and the outputs of data selectors 41 and 42, and is therefore equal to a.sub.1 a.sub.2 a.sub.3 0000000000000.

At the second clock tick the next variable-length codeword, on leads 34, is b.sub.1 b.sub.2 b.sub.3 b.sub.4 0000, with a codeword length of 4 on leads 18. The previous adder output, 3, is entered into adder latch 33, and carry latch remains 0. The eight most significant bits of the previous OR circuit output 51 are entered in upper latch 53, and the eight least significant bits of the previous OR circuit output 52 are entered in lower latch 54, or a.sub.1 a.sub.2 a.sub.3 00000 and 00000000, respectively. The output register 57 still contains noise. Adder 31 sums the current codeword length of 4 with the 3 in adder latch 33, to produce 7 on leads 32. Carry remains 0. With the shift value output of adder latch 33 being 3, cross bar shift control circuit 30 shifts its input by three bits to produce an output of 000b.sub.1 b.sub.2 b.sub.3 b.sub.4 000000000. Data selector 41 selects the sequence in upper latch 53 for its output, or a.sub. 1 a.sub.2 a.sub.3 00000, and data selector 42 selects the sequence in lower latch 54 for its output, or 00000000. The 16-bit output of OR circuit 38 is the sum of the combined data selector outputs and the cross bar shift control circuit output 40, or a.sub.1 a.sub.2 a.sub.3 b.sub.1 b.sub.2 b.sub.3 b.sub.4 000000000. As can be noted, the OR circuit 38 has concatenated the second variable-length codeword to the significant non-filler bits of the first variable-length codeword.

At the third clock tick the variable-length input codeword on leads 17 is c.sub.1 c.sub.2 c.sub.3 c.sub.4 c.sub.5 c.sub.6 00, with a corresponding codeword length of 6 on leads 18. Adder latch 33, and thus the shift value, is the previous output of adder 31, or 7. Carry latch still remains 0. The eight upper bits of the previous OR circuit output 51, a.sub.1 a.sub.2 a.sub.3 b.sub.1 b.sub.2 b.sub.3 b.sub.4 0, are entered in upper latch 53, and the eight lower bits, 00000000, are entered in lower latch 54. Output register 57 still contains noise. The output of adder 31 is the modulo-8 sum of the current codeword length, 6, plus the adder latch 33 output of 7, for a total of 5 with a carry of 1. Cross bar shift control circuit 30 shifts the input word by the shift value of 7 to produce an output of 0000000c.sub.1 c.sub.2 c.sub.3 c.sub.4 c.sub.5 c.sub.6 000 . Data selector 41 selects the sequence in upper latch 53 and data selector 42 selects the sequence in lower latch 54. The OR circuit 38 combines the outputs of data selectors 41 and 42 with the output of cross bar shift control circuit 40 to produce an output of a.sub.1 a.sub.2 a.sub.3 b.sub.1 b.sub.2 b.sub.3 b.sub.4 c.sub.1 c.sub.2 c.sub.3 c.sub.4 c.sub.5 c.sub.6 000.

At the forth clock tick the input word is d.sub.1 d.sub.2 d.sub.3 00000, having a codeword length of 3. The adder latch 33, and thus the shift value, is the previous output of adder 31, equal to 5. Since the carry was 1 at the previous clock tick, carry latch 36 is 1 at this clock tick. Upper latch 53 receives the upper 8-bits of the previous OR circuit 38 output, or a.sub.1 a.sub.2 a.sub.3 b.sub.1 b.sub.2.sbsb.3 b.sub.4 c.sub.1, and lower latch 54 receives the lower 8-bits of the OR output, or c.sub.2 c.sub.3 c.sub.4 c.sub.5 c.sub.6 000. The output register 57 still contains noise and the output of adder 31 is the sum of the current codeword length, 3, with the contents of adder latch 33, 5, for a total of 0 with a carry of 1. The cross bar circuit 30 output is shifted by the shift value of 5 to produce an output of 00000d.sub.1 d.sub.2 d.sub.3 00000000. Since the carry latch is now 1, however, data selector 41 selects the contents of lower latch 54 for its output, c.sub.2 c.sub.3 c.sub.4 c.sub.5 c.sub.6 000, and data selector 42 selects all 0s from inputs 55. The OR circuit 38 output is thus c.sub.2 c.sub.3 c.sub.4 c.sub.5 c.sub. 6 d.sub.1 d.sub.2 d.sub.3 00000000.

At the fifth clock tick the input variable-length codeword is e.sub.1 e.sub.2 e.sub.3 e.sub.4 0000, having a length of 4. The adder latch 33 output, and thus the shift value, is the previous output of adder 31 output, or 0. Since the previous carry was 1, carry latch 36 remains at 1. The upper latch 53 is the upper 8-bits of the previous OR circuit 38 output, or c.sub.2 c.sub.3 c.sub.4 c.sub.5 c.sub.6 d.sub.1 d.sub.2 d.sub.3, and the lower latch 54 is the lower 8-bits of the OR output, or 00000000. Since the previous carry latch was 1, output register 57 receives the previous upper latch value of a.sub.1 a.sub.2 a.sub.3 b.sub.1 b.sub.2 b.sub.b.sbsb.4 c.sub.1. The output of adder 31 is now 4 with a carry of 0. With a shift of 0, the cross bar control circuit output is e.sub.1 e.sub.2 e.sub.3 e.sub.4 000000000000. Since carry latch is 1, data selector 41 selects the lower latch for its output of 00000000, and data selector 42 selects all "0"s from leads 55 for its outputs. The OR circuit 38 output is thus equal to the output of cross bar shift control circuit 30, e.sub.1 e.sub.2 e.sub.3 e.sub.4 000000000000.

At the sixth clock tick, the previous carry latch was 1 so that the output register 57 receives the segment in the upper latch at the fifth clock tick, or c.sub.2 c.sub.3 c.sub.4 c.sub.5 c.sub.6 d.sub.1 d.sub.2 d.sub.3.

At the seventh clock tick, the previous carry latch is 0 so that output register 57 retains its previous value, indicated in FIG. 5 with a "-" in the "output register" column. Similarly, at the eighth clock tick, the previous carry latch is still 0 and output register 57 remains unchanged. At the ninth clock tick, however, the previous clock tick is 1 and the next sequential 8-bit segment, e.sub.1 e.sub.2 e.sub.3 e.sub.4 f.sub.1 f.sub.2 g.sub.1 g.sub.2, is entered into output register 57.

From the above-described example, it is evident how the sequential variable-length codewords are concatenated and how, each time 8-bits are accumulated, an 8-bit segment is outputted for storage in the buffer 23.

In the embodiment of the present invention described hereinabove, each output segment is equal in length to the maximum variable-length codeword length, which in the described embodiment is 8-bits. In an actual circuit, however, the maximum length codeword can be generalized to be N-bits, and the length of each output segment can be M-bits, where M.gtoreq.N. In this general case the adder 31 and adder latch 33 count codeword lengths modulo-M. The cross bar shift control circuit 30 has an N-bit input and an (M+N)-bit output. Upper latch 53 stores M-bits and lower latch 54 stores N-bits. When the carry latch signal 37 is "1" and data selector 41 selects the contents of lower latch 54 to output, an additional (M-N) "0"-bits are inserted following the N-bits from lower latch 54 so that a total of M-bits are output by that data selector. This is shown in FIG. 2 with dotted input leads 60 of "0" inputs to data selector 41.

The above-described embodiment is illustrative of the principles of the present invention. Other embodiments could be devised by those skilled in the art without departing from the spirit and scope of the present invention.