Abstract:
A runlength coding method converts an input data stream including a multiplicity of zeros and non-zero values to a runlength coded signal. A first sequence and a second sequence are generated based on the input data stream, and then first and second count control information and also add control information are produced based on the data in the first and the second sequences. In response to the first count control information, the number of zeros in the first sequence is calculated to thereby provide a first counted value and the number of zeros in the second sequence is computed responsive to the second count control information so as to supply a second counted value. The determined counted values are summed and provided as a runlength in response to the add control information, wherein the runlength represents the number of zeros in a run of continuous zeros preceding a non-zero value in the input data stream.

Description:
FIELD OF THE INVENTION 
     The present invention relates to a method and apparatus for encoding a digital video signal; and, more particularly, to an improved runlength coding method and apparatus for use in a video signal encoding system. 
     DESCRIPTION OF THE PRIOR ART 
     As is well known, transmission of digitized video signals can attain video images of a much higher quality than the transmission of analog signals. When an image signal is expressed in a digital form, a substantial amount of data is generated for transmission, especially in the case of a high definition television(HDTV) system. Since, however, the available frequency bandwidth of a conventional transmission channel is limited, in order to transmit the substantial amounts of digital data therethrough, it is inevitable to compress or reduce the volume of the transmission data. 
     In a modern video image transmission or processing system, a digital video signal may be coded by first obtaining a discrete cosine transform(DCT) of a block of pixels. The DCT, which reduces or removes spatial redundancies between frames of image data, converts a block of digital image data, for example, a block of 8×8 pixels, into a set of transform coefficient data. The transform coefficient data is quantized so as to take advantage of the occurrence of &#34;zeros&#34; and then zigzag scanned, thereby generating a stream of image data having a plurality of zeros and non-zero values. Thereafter, the data stream is subjected to a runlength coding to exploit runs of zeros in this data stream. 
     As shown in FIG. 1, a conventional apparatus employing the runlength coding comprises a first buffer 11, a zero value detector 12, a counter 13 and a second buffer 14. The first buffer 11 stores the data stream temporarily and sequentially supplies it to the zero value detector 12 and the second buffer 14 in parallel. The zero value detector 12 checks whether the element of the data stream fed thereto is zero or not and outputs the result to the counter 13 and the second buffer 14 as a control signal. The counter 13 counts the number of elements of the data stream detected as zero at the zero value detector 12 and outputs the number as a runlength under the instruction of the control signal. In response to the control signal from the zero value detector 12, the second buffer 14 outputs a non-zero value of the data stream as a level corresponding to the runlength retrieved from the counter 13. Consequently, the data stream is converted into a multiplicity of run-level pairs, each of the run-level pairs including a runlength and a corresponding level, wherein the runlength represents the number of zeros in a run of continuous zeros preceding a non-zero value and the level indicates the magnitude of the non-zero value following the run of continuous zeros. 
     Since, however, the conventional apparatus processes each element in the data stream in a series fashion, it remains desirable to develop a method of further improving the data processing speed. 
     SUMMARY OF THE INVENTION 
     It is, therefore, a primary object of the invention to provide a runlength coding method and apparatus capable of converting at an improved speed an input data stream to a multiplicity of run-level pairs. 
     In accordance with the present invention, there is provided a runlength coding apparatus for encoding an input data stream of image data, wherein the input data stream includes a plurality of zeros and non-zero values, which comprises: an input buffer for generating a first sequence and a second sequence of the input data stream, the first and the second sequences including (2M-1)st data and (2M)th data in the input data stream, respectively, M being a positive integer; a control circuit for providing first and second count control information and also add control information based on the data in the first and the second sequences; a first counter for calculating, in response to the first count control information, the number of zeros in the first sequence to thereby provide a first counted value; a second counter for computing, in response to the second count control information, the number of zeros in the second sequence to thereby supply a second counted value; and an addition block for summing up the first and second counted values and outputting the sum as a runlength in response to the add control information, wherein the runlength represents the number of zeros in a run of continuous zeros preceding a non-zero value in the input data stream. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above and other objects and features of the present invention will become apparent from the following description of preferred embodiments given in conjunction with the accompanying drawings, in which: 
     FIG. 1 shows a schematic block diagram of a conventional runlength coding apparatus; 
     FIG. 2 depicts a runlength coding apparatus in accordance with the present invention; and 
     FIGS. 3A to 3F represent exemplary state maps in order to generate control signals for controlling the apparatus in FIG. 2. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring to FIG. 2, there is shown a runlength coding apparatus in accordance with a preferred embodiment of the present invention. The runlength coding apparatus 100 encodes an input image data stream to provide a runlength coded signal, wherein the input data stream includes a plurality of zeros and non-zero values. 
     As shown in FIG. 2, an input data stream is fed to an input buffer 10 for a rearrangement and temporary storage thereof. At the input buffer 10, the input data stream coupled thereto is broken up into an odd sequence and an even sequence of the input data stream, wherein the odd sequence includes (2M-1)st data of the input data stream and the even sequence has (2M)th data of the input data stream, M being a positive integer. Then, the odd sequence is coupled to a first zero value detector 20A and a multiplexer 60 via a line L50, while the even sequence is fed to a second zero value detector 20B and the multiplexer 60 via a line L60. 
     The first zero value detector 20A generates a current detection value Q1 with a logic low, i.e., a digit &#34;0&#34;, to a controller 30 if the (2M-1)st data of the input data stream retrieved from the input buffer 10 is zero; and provides a logic high, i.e., a digit &#34;1&#34; to the same if the (2M-1)st data is a non-zero value. In the same fashion, a current detection value Q2 supplied from the second zero value detector 20B to the controller 30 varies depending on the (2M)th data of the input data stream from the input buffer 10. In the meantime, the first zero value detector 20A also generates a first write signal WRITE1 to a first and a second counters 40A and 40B through a line L10, and the second zero value detector 20B provides a second write signal WRITE2 to the first and second counters 40A and 40B through a line L20. The first and second write signals WRITE1 and WRITE2 have the same patterns as the first and second detection values Q1 and Q2, respectively. 
     The controller 30 generates control signals to control the first and second counters 40A and 40B, an addition block 50 and the multiplexer 60 based on the current detection values Q1 and Q2 and previous detection values Q1&#39; and Q2&#39; from the previous operation cycle, produced at the first and second zero value detectors 20A and 20B, respectively. 
     First of all, the controller 30 supplies respective counter control signals to the first and second counters 40A and 40B so as to adjust the count operation therein. Each of the counter control signals for the counters 40A and 40B includes, e.g., a set signal S, a reset signal R and a count signal C, i.e., S1, R1 and C1 for the first counter 40A and S2, R2 and C2 for the second counter 40B. The set signal S controls each counter to set a current counted value of each counter to 1; the reset signal R manages each counter to reset the current counted value to zero; and the count signal C adjusts each counter to increase a previous counted value by one to thereby update the current counted value when each of the signals S, R and C is enabled as a logic high. In order to control the counters, only one signal of the signals S, R and C for each counter is enabled at a time. The signals to be enabled for the counters are determined based on an excitation table as shown in  TABLE 1!. 
     
                       TABLE 1______________________________________                            OUTPUTPREVIOUS          CURRENT        SIGNALSQ1&#39;    Q2&#39;        Q1    Q2       1st 2nd______________________________________0      0          0     0        C1  C20      0          0     1        R1  R20      0          1     0        R1  S20      0          1     1        R1  R20      1          0     0        S1  S20      1          0     1        R1  R20      1          1     0        R1  S20      1          1     1        R1  R21      0          0     0        S1  C21      0          0     1        R1  R21      0          1     0        R1  S21      0          1     1        R1  R21      1          0     0        S1  S21      1          0     1        R1  R21      1          1     0        R1  S21      1          1     1        R1  R2______________________________________ 
    
     In the  TABLE 1!, each of the output signals represents a logic high, i.e., an enabled state. 
     The  TABLE 1! can be described as a state map for each of the signals C1, C2, R1, R2, S1 and S2 shown in FIGS. 3A to 3F. Referring to the  TABLE 1! and the maps in FIGS. 3A to 3F, each of the output signals is depicted as follows: 
     S1=Q1&#39;*/Q1*/Q2+/Q1,*Q2&#39;*/Q1*/Q2  EQ1-a! 
     S2=Q2&#39;*/Q1*/Q2+Q1*/Q2  EQ2-a! 
     R1=Q1+/Q1*Q2  EQ1-b! 
     R2=Q2  EQ2-b! 
     C1=/Q1&#39;*/Q2&#39;*/Q1*/Q2  EQ1-c! 
     C2=/Q2&#39;*/Q1*/Q2  EQ2-c! 
     wherein /Qi and /Qi&#39; represent the complements of Qi and Qi&#39;, respectively; and i is either 1 or 2. 
     In the preferred embodiment of the present invention, the controller 30 for generating the counter control signals is constructed as a gate array based on the state equations  EQ1-a! to  EQ2-c!. 
     Therefore, the first and second counters 40A and 40B accomplish their count operations in response to the control signals from the controller 30 and output their counted values to the addition block 50 if at least one of the write signals WRITE1 and WRITE2 is enabled. 
     The controller 30 also provides the addition block 50 with an increment signal through a line L40 in order to increase an added counted value of the addition block 50 by one only if the current first and second detection values Q1 and Q2 from the first and second zero value detectors 20A and 20B, respectively, have digits &#34;0&#34; and &#34;1&#34;, separately, wherein the added counted value is a sum of the counted values retrieved from the first and second counters 40A and 40B; and generates an add control signal, which is enabled when at least one of Q1 and Q2 has a digit 11111, to the addition block L50 through the line L70. More specially, the add control signal is produced to control the addition block 50 which outputs a previous added counted value as a runlength when the Q1, Q2 are either 0, 1 or 1, 0, respectively, and, when each of Q1 and Q2 has a digit value &#34;1&#34;, provides a previous added counted value and a current added counted value as runlengths, respectively, the previous added counted value being a sum of counted values from the first and second counters 40A and 40B based on the previous detection values Q1&#39; and Q2&#39; and the current added value being determined by the current detection values Q1 and Q2. 
     Meanwhile, the controller 30 also provides a selecting signal via a line L30, which is enabled when at least one of Q1 and Q2 has a digit &#34;1&#34;, to the multiplexer 60 for producing at least one non-zero value of data received from the lines L50 and L60 as a level. That is, likewise at the addition block 50, the selecting signal has a signal pattern to control the multiplexer 60 which outputs a non-zero value received from the lines L50 and L60 as a level if the Q1, Q2 are either 0,1 or 1,0, respectively, and sequentially provides non-zero values received from the lines L50 and L60 as levels if each of Q1 and Q2 has a digit &#34;1&#34;, wherein a non-zero value from the line L60 always follows a non-zero value from the line L50. 
     In this way, a sequence of run-level pairs is constructed from the input data stream to thereby produce a runlength coded signal. 
     The operation of the runlength coding apparatus may be more readily understood with reference to an example provided below. Assuming that the input data stream inputted to the input buffer 10 shown in FIG. 2 consists of the sequence, &#34;0, 0, 0, 1 1 , 0, 0, 1 2 , 0, 0, 0, 1 3 , 1 4 , 0, 0, . . . &#34; and both of the counters 40A and 40B are initially reset to zero, wherein 1 1 , 1 2 , 1 3 , and 1 4  are non-zero values. 
     The sequence of input data stream is separated into an odd sequence and an even sequence such as &#34;0, 0, 0, 1 2 , 0, 1 3 , 0, . . . &#34; and &#34;0, 1 1  0, 0, 0, 1 4 , 0 . . . &#34;, respectively, at the input buffer 10 and each value of the odd and even sequences is provided to the first and second detectors 20A and 20B and the multiplexer 60 as before-mentioned. 
     At the first operation cycle, the first values 0 and 0 in the odd and even sequences are coupled to the first and second zero value detectors 20A and 20B, respectively, at the same time. Then, the first zero value detector 20A produces the first detection value Q1 with a digit &#34;0&#34; and the second zero value detector 20B supplies the second detection value Q2 of a digit &#34;0&#34; based on the first values 0 and 0. In the mean time, the first and second zero value detectors 20A and 20B also generate the first and second write signals WRITE1 and WRITE2 with a logic low, i.e., disabled. The controller 30 provides enabled set signals S1 and S2 to the first and second counters 40A and 40B, separately, by comparing the current detection values Q1 and Q2 having a digit &#34;0&#34; with the initial detection values Q1&#39; and Q2&#39;, which are initially set to a digit &#34;1&#34;; supplies disabled increment and add control signals to the addition block 50 to thereby prevent the addition block 50 from providing a previous or current added counted value as a runlength; and also controls the multiplexer 60 to be incapacitated by a disabled selecting signal. Then, the first and second counters 40A and 40B produce current counted values 1&#39;s in response to the enabled set signals S1 and S2, respectively. The current counted values, i.e., 1 and 1 generated at the first and second counters 40A and 40B are temporarily stored therein as previous counted values until a next enabled write signal is coupled thereto since the counters 40A and 40B cannot transfer the current counted values to the next device due to the disabled current write signals WRITE1 and WRITE2. In the above operation cycle, the current detection values Q1 and Q2 used at the controller 30 are also stored at the controller 30 to be used as the previous detection values Q1&#39; and Q2&#39; at the next operation cycle. 
     In the same manner as at the first operation cycle, at the second operation cycle, the second values 0 and 1 1  of the odd and even sequences, respectively, are separately coupled to the first and second zero value detectors 20A and 20B. The first and second zero value detectors 20A and 20B produce the current detection values Q1 and Q2 having digits &#34;0&#34; and &#34;1&#34;, respectively; and, also generate the first write signal WRITE1 disabled and the second write signal WRITE2 enabled. The controller 30 provides the enabled R1 and R2 signals to the first and second counters 40A and 40B, individually, according to the  TABLE 1!, by comparing the current detection values Q1, Q2 having 0, 1 with the previous detection values Q1&#39;, Q2&#39; containing 0, 0 generated during the first operation cycle and stored at the controller 30; supplies enabled increment and add control signals to the addition block 50, wherein, as before-mentioned, the increment signal is enabled because the current detection values Q1 and Q2 have respective digits &#34;0&#34; and &#34;1&#34;; and also outputs an enabled selecting signal to the multiplexer 60. Accordingly, the addition block 50 increases the previous added counted value by one and outputs the increased value, i.e., 3 as a runlength at that time, the previous added counted value being a sum of the counted values from the counters 40A and 40B, i.e., 2 because the counted values of the counter 40A and 40B were set as 1 at the previous operation cycle by the enabled signals S1 and S2. Meanwhile, the multiplexer 60 provides the non-zero value 11 as a level in response to the enabled selecting signal from the controller 30. Then, the counter 40A and 40B are reset by the enabled signals R1 and R2. As a result of the second operation cycle, a run-level pair (3, 1 1 ) having the run-length 3 and the level 11 is produced. 
     At the third operation cycle, the first and second zero value detectors 20A and 20B produce the current detection values Q1 and Q2, each having a digit &#34;0&#34;, and the disabled write signals WRITE1 and WRITE2 based on the third values 0 and 0 of the odd and even sequences fed thereto, respectively. At the controller 30, the enabled S1 and S2 signals are produced based on Q1&#39;, Q2&#39; having 0, 1 and Q1, Q2 with 0, 0, respectively, as shown in the  TABLE 1!; disabled increment and add control signals are supplied to the addition block 50; and a disabled selecting signal is coupled to the multiplexer 60. Thereafter, the addition block 50 does not output any added counted value due to the disabled add control signal and the multiplexer 60 is also incapacitated in response to the disabled selecting signal. Then, the counter 40A and 40B are set by the enabled signals S1 and S2 and, thus, the counted values 1&#39;s are stored at the first and second counters 40A and 40B, separately, as the previous counted values. 
     During the fourth operation cycle, the fourth values 1 2  and 0 of the odd and even sequences are transferred to the first and second zero value detectors 20A and 20B. Accordingly, Q1 having a digit &#34;1&#34; and Q2 containing a digit &#34;0&#34; are produced and an enabled WRITE1 signal and a disabled WRITE2 signal are generated. Based on the Q1, Q2, WRITE1 and WRITE2 signals, the controller 30 provides enabled R1 and S2 signals to the first and second counters 40A and 40B, respectively; supplies an enabled add control signal to the addition block 50; and outputs an enabled selecting signal to the multiplexer 60. The addition block 50 calculates a sum of the previous counted values, e.g., 1 and 1, of the first and second counter 40A and 40B and outputs the sum, i.e., 2 as a runlength responsive to the enabled add control signal from the controller 30. Concurrently, the multiplexer 60 provides the non-zero value 1 2  as a level under the control of the enabled selecting signal from the controller 30. Then, the first counter 40A is reset by R1 and the second counter 40B is set by S2. Through the fourth operation cycle, a second run-level pair (2, 1 2 ) is constructed. 
     The fifth operation cycle based on the fifth values 0 and 0 retrieved from the input buffer 10 is also accomplished in the similar manner as used in the above operations. That is, since Q1&#39;, Q2&#39;, Q1 and Q2 have corresponding values 1, 0, 0 and 0, S1 and C2 are enabled as shown in the  TABLE 1! and both WRITE1 and WRITE2 are disabled. Therefore, the addition block 50 and the multiplexer 60 do not provide a runlength and a level. The first counter 40A contains a counted value 1 by being set and the second counter 40B has a counted value 2 by incrementing the previous counted value 1 by one. 
     At a subsequent cycle, the non-zero values 13 and 14 are fed to the first and second zero value detectors 20A and 20B and, thus, enabled write signals WRITE1 and WRITE2 are produced to thereby operate on the first and second counters 40A and 40B. And, the controller 30 generates enabled R1 and R2 signals. Since, however, at this operation cycle, each of the detection values Q1 and Q2 has a value &#34;1&#34;, the add control signal and the selecting signal have to be enabled twice to thereby sequentially output the non-zero values 1 3  and 1 4  as a level, wherein the twice enabled add control signal and the selecting signal need to have an appropriate time interval between the first and second enabled signals, the time interval being long enough for the current counted values to be determined at the first and second counters 40A and 40B by the enabled R1 and R2 signals, separately. That is, the first enabled add control and selecting signals control the addition block 50 and the multiplexer 60 to construct a first run-level pair based on the non-zero value 13 and the previous counted values, i.e., 1 and 2 stored at the first and second counters 40A and 40B. On the other hand, the second enabled add control and selecting signals have the addition block 50 and the multiplexer 60 to generate a second run-level pair based on the non-zero value 1 4  and the current counted values, i.e., 0 and 0 respectively produced at the first and second counters 40A and 40B by the enabled signals R1 and R2. Hence, at this operation cycle, the apparatus 100 provides two run-level pairs, a first one (3, 1 3 ) and a second one (0, 1 4 ). 
     The rest of the outputs of the input buffer 10 are also converted to a sequence of run-level pairs through the same or similar manner as used at the above processes based on the  TABLE 1!. 
     As a result, the sequence &#34;0, 0, 0, 1 1 , 0, 0, 1 2 , 0, 0, 0, 13, 1 4 , 0, 0, . . . &#34; is converted to run-level pairs (3, 1 1 ), (2, 1 2 ), (3, 1 3 ), (0, 1 4 ), etc. to thereby produce the runlength coded signal through the runlength coding method and apparatus proposed by the present invention. 
     While the present invention has been shown and described in connection with the preferred embodiments only, it will be readily apparent to those of ordinary skill in the art that many changes and modifications may be made without departing from the spirit and scope of the invention as defined in the appended claims.