Variable-length encoder and decoder using symbol/code-word re-association of a coding table

Abstract

A variable-length encoder using a code table having a symbol/code-word re-association feature, which includes a first storing portion for storing previously generated code table information, a first re-associating portion for generating re-associated code table information and re-association information indicative of the relation between a symbol and a corresponding code word from a previously generated code table information stored in the first storing portion, based on the frequency of occurrence of externally applied symbols during a predetermined time period, a delay for delaying and outputting the same symbols as those input to the first re-associating portion during the predetermined time period, a re-association information storing portion for storing the re-associated code table information and re-association information and sequentially outputting the re-association information, a variable-length encoder for receiving the symbols stored in the delay and generating and sequentially outputting code words according to the re-associated code table information stored in the re-association information storing portion, and a multiplexer which outputs the re-association information from the re-association information storing portion and the code words output from the variable-length encoder, to thereby reduce the code length of code words generated by variable-length encoding even when the frequency of occurrence of symbols used in forming a previously generated code table is different from that of the symbols applied during the predetermined time period.

What is claimed is:  
     
       1. A variable-length code word transmission system, comprising: 
       encoder means for receiving and encoding input symbols into variable-length code words based on a frequency of occurrence of said symbols, said encoder means including  
       means for re-associating a relationship between code words and each distinct received symbol and generating re-association information for each distinct received symbol; and  
       means for transmitting said re-association information generated by said means for re-associating and said variable-length code words in an alternating manner; and  
       decoder means for decoding the transmitted variable-length code words based on said transmitted re-association information.  
     
     
       2. The variable-length code word transmission system claimed in  claim 1 , wherein said encoder means further comprises: 
       fast storing means for storing a previously generated code table;  
       first re-associating means for receiving externally applied symbols during a predetermined time period, generating a re-associated code table and re-association information indicative of a relation between a symbol and a corresponding code word from said previously generated code table stored in said first storing means, based on the frequency of occurrence of the externally applied symbols during a predetermined time period;  
       delay means for delaying and outputting the same symbols as those input to said first re-associating means during the predetermined time period;  
       re-association information storing means for storing said re-associated code table and re-association information for each distinct received symbol and sequentially outputting said re-association information;  
       variable-length coding means for receiving said symbols output from said delay means and generating and sequentially outputting code words according to said re-associated code table stored in said re-association information storing means; and  
       means for multiplexing and outputting said re-association information from said re-association information storing means and said code words output from said variable-length coding means.  
     
     
       3. The variable-length code word transmission system claimed in  claim 1 , wherein said decoder means comprises: 
       storing means for storing the same code table as that previously generated and stored in the encoder means;  
       demultiplexing means for receiving data output from the encoder means, and dividing and outputting symbol/code-word re-association information and code words from the received data;  
       re-associating means for receiving said re-association information from said demultiplexing means, re-associating a code-word and a corresponding symbol, and storing said re-associated code table; and  
       variable-length decoding means for decoding said code words based on said code table stored in said re-associating means to thereby generate a symbol.  
     
     
       4. The variable-length code word transmission system as claimed in  claim 1 , wherein said encoder means is a Huffman variable-length encoder. 
     
     
       5. The variable-length code word transmission system as claimed in  claim 1 , wherein said decoder means is a Huffman variable-length decoder. 
     
     
       6. The variable-length code word transmission system claimed in  claim 1 , wherein said means for transmitting transmits said re-association information whenever a corresponding variable-length code word is transmitted. 
     
     
       7. A variable-length encoder using symbol/code-word re-association of a code table comprising: 
       delay means for delaying externally applied symbols;  
       first storing means for storing a previously generated code table;  
       first re-associating means for generating a re-associated code table and re-association information indicative of the relation between one of said symbols and a corresponding code word from said previously generated code table stored in said first storing means, based on a frequency of occurrence of the externally applied symbols during a predetermined time period, wherein said first re-associating means generates re-association information for each different one of the externally applied symbols;  
       re-association information storing means for storing said re-associated code table and said re-association information, and sequentially outputting said re-association information;  
       variable-length encoding means for receiving the delayed symbols and generating and sequentially outputting code words according to said re-associated code table stored in said re-association information storing means; and  
       means for multiplexing and outputting said re-association information output from said re-association information storing means, and said code words output from said variable-length encoding means in an alternating manner.  
     
     
       8. The variable-length encoder using a symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said first re-associating means re-associates said symbols to said code words of said previously generated code word table stored in said first storing means so that, for symbols used in re-association of the code table, a symbol having a higher frequency of occurrence is associated with a code word having a shorter length. 
     
     
       9. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said first re-associating means comprises: 
       a plurality of symbol counters for counting the number of each symbol applied during the predetermined time period and storing the counted values for each of the respective symbols, said first re-associating means generating the re-associated code table and re-association information from a previously generated code table, based on the counted values.  
     
     
       10. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said predetermined time period is a time period required to re-associate symbols to code words of a code table by using symbols obtained from one slice of video data. 
     
     
       11. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said predetermined time period is a time period required to re-associate symbols to code words of a code table by using symbols obtained from one frame of video data. 
     
     
       12. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said re-association information storing means outputs corresponding re-association information to said multiplexing means whenever during the predetermined interval a code word is first output from said variable-length coding means. 
     
     
       13. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said re-association information storing means outputs only one set of re-association information to said means for multiplexing with respect to a plurality of the same code words. 
     
     
       14. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said means for multiplexing outputs the re-association information corresponding to a code word prior to outputting the corresponding code word. 
     
     
       15. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said re-association information storing means outputs re-association information corresponding to each code word to said multiplexing means in order in which the distinnct symbols occurs. 
     
     
       16. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 7 , wherein said variable length encoding means is a Huffman encoder. 
     
     
       17. The variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 4 , wherein said means for multiplexing and outputting outputs said re-association information whenever a corresponding code word is transmitted. 
     
     
       18. A variable-length decoder for decoding output from a variable-length encoder using symbol/code-word re-association of a code table, the encoder having a previously generated code table stored in a code table, and which outputs data including code words and symbol/code-word re-association information, the decoder comprising: 
       storing means for storing the same code table as that previously generated and stored in the variable-length encoder;  
       demultiplexing means for receiving data output from the variable-length encoder, and dividing and outputting symbol/code-word re-association information and code words from the received data, wherein the symbol/code word re-association information for one of the code words is received only when the code word is received for the first time during a predetermined time interval and before another code word is received;  
       re-associating means for receiving said re-association information from said demultiplexing means, re-associating a code-word and a corresponding symbol, and storing said re-associated code table information; and  
       variable-length decoding means for decoding the code words based on said code table information stored in said re-associating means to thereby generate a symbol.  
     
     
       19. The variable-length decoder as claimed in  claim 18 , wherein said re-associating means re-associates a code word and a symbol only when said code word has been received and before said another code word is received. 
     
     
       20. The variable-length decoder for decoding the output from a variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 18 , wherein said variable-length decoding means is a Huffman decoder. 
     
     
       21. The variable-length decoder for decoding the output from a variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 18 , wherein said pre-determined time interval is a time period for one slice of video data. 
     
     
       22. The variable-length decoder for decoding the output from a variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 18 , wherein said pre-determined time interval is a time period for one frame of video data. 
     
     
       23. A variable-length decoder for decoding output from a variable-length encoder using symbol/code-word re-association of a code table, the encoder having a previously generated code table stored in a code table, and which outputs data including code words and symbol/code-word re-association information, the decoder comprising: 
       storing means for storing the same code table as that previously generated and stored in the variable-length encoder;  
       demultiplexing means for receiving data output from the variable-length encoder, and dividing and outputting symbol/code-word re-association information and code words from the received data, wherein said code words and said symbol/code-word re-association information are received in an alternating manner, and symbol/code-word re-association information for any one of the code words is received before said code words are received;  
       re-associating means for receiving said re-association information from said demultiplexing means, re-associating a code word and a corresponding symbol when said code word is first received, and storing said re-associated code table information; and  
       variable-length decoding means for decoding the code word based on the code table information stored in said re-associating means to thereby generate a symbol.  
     
     
       24. The variable-length decoder for decoding output from a variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 23 , wherein said variable-length decoding means is a Huffman decoder. 
     
     
       25. The variable-length decoder for decoding output from a variable-length encoder using symbol/code-word re-association of a code table as claimed in  claim 23 , wherein said demultiplexing means receives symbol/code-word re-association information whenever a corresponding code word is received. 
     
     
       26. A variable-length encoding method, comprising: 
       receiving input data;  
       delaying the received input data for a pre-determined time period;  
       counting occurrences of each distinct input data using the delayed input data;  
       re-associating a relationship between code words and each distinct received input data based on the counted occurrence of each distinct input data, and generating re-association information for each distinct received input data, wherein the code words are read from a previously generated code book;  
       encoding said received input data using the re-associated relationship and outputting selected code words; and  
       transmitting said re-association information and the selected code words in an alternating manner.  
     
     
       27. A variable-length encoding method as claimed in  claim 26 , wherein said re-associating is carried out at a pre-determined time interval. 
     
     
       28. A variable-length encoding method as claimed in  claim 27 , wherein said pre-determined time interval is a time period for one slice of video data. 
     
     
       29. A variable-length encoding method as claimed in  claim 27 , wherein said pre-determined time interval is a time period for one frame of video data. 
     
     
       30. A variable-length decoding method, comprising: 
       receiving interleaved re-association information and code word data and separating said re-association information and said code word data;  
       generating a re-associated code book by modifying association of code words and symbol data as defined in a previously generated code book using said re-association information; and  
       decoding said received code word data using said re-associated code book and outputting decoded data.  
     
     
       31. A variable-length decoding method as claimed in  claim 30 , wherein said re-association information is received only for distinct received code word data. 
     
     
       32. A variable-length decoding method as claimed in  claim 30 , wherein said re-association information is received for each received code word data. 
     
     
       33. A variable-length decoding method as claimed in  claim 30 , wherein said generating a re-associated code book is carried out at a pre-determined time interval. 
     
     
       34. A variable-length decoding method as claimed in  claim 33 , wherein said pre-determined time interval is a time period for one slice of video data. 
     
     
       35. A variable-length decoding method as claimed in  claim 33 , wherein said pre-determined time interval is a time period for one frame of video data. 
     
     
       36. A digital data transmission method, comprising: 
       receiving input data;  
       delaying the received input data for a pre-determined time period;  
       counting occurrences of each distinct input data using the delayed input data;  
       re-associating a relationship between code words and each distinct received input data based on the counted occurrence of each distinct input data, and generating re-association information for each distinct received input data, wherein the code words are read from a previously generated code book;  
       encoding said received input data using the re-associated relationship and outputting selected code words;  
       transmitting said re-association information and the selected code words in an alternating manner;  
       receiving the re-association information and code word data and separating said re-association information and said code word data;  
       generating a re-associated code book by modifying associations of code words and symbol data as defined in a previously generated code book using said re-association information; and  
       decoding said received code word data using said re-associated code book and outputting decoded data.  
     
     
       37. A variable- length encoding method, comprising:    
       
         receiving input symbol data;  
       
         adapting a relationship between each distinct received input symbol data and variable - length code words and generating adapted association information for each distinct received input symbol data;    
       
         generating a current code book, having a different association of code words and symbol data as compared to a previously generated code book, in accordance with said adapted association information;  
       
       
         variable length coding said input symbol data into variable length code words using said current code book to generate variable length code words; and  
       
       
         transmitting said adapted association information and said variable length code words in an alternating manner. 
       
     
     
       38. The variable- length encoding method as claimed in    claim 37   , wherein the code words of said current code book and said previously generated code book are identical.   
     
     
       39. The variable- length encoding method as claimed in    claim 38   , wherein said generating a current code book is carried out at a predetermined interval.   
     
     
       40. The variable- length encoding method as claimed in    claim 39   , wherein said predetermined interval is for one slice of video data.   
     
     
       41. The variable- length encoding method as claimed in    claim 39   , wherein said predetermined interval is for one frame of video data.   
     
     
       42. The variable- length encoding method as claimed in    claim 39   , wherein said predetermined interval is for one field of video data.   
     
     
       43. A variable- length decoding method, comprising:    
       
         receiving interleaved adapted association information and code word data;  
       
       
         generating a current code book, having a different association of code words and symbol data as compared to a previously generated code book, in accordance with said adapted information; and  
       
       
         decoding said received code word data using said current code book and outputting decoded data. 
       
     
     
       44. The variable- length decoding method as claimed in    claim 43   , wherein the code words of said current code book and said previously generated code book are identical.   
     
     
       45. The variable- length decoding method as claimed in    claim 44   , wherein said generating a current code book is carried out at a predetermined interval.   
     
     
       46. The variable- length decoding method as claimed in    claim 45   , wherein said predetermined intervals is for one slice of video data.   
     
     
       47. The variable- length decoding method as claimed in    claim 45   , wherein said predetermined interval is for one frame of video data.   
     
     
       48. The variable- length decoding method as claimed in    claim 45   , wherein said predetermined interval is for one field of video data.   
     
     
       49. A variable- length decoding method, comprising:    
       
         receiving interleaved adapted association information and code word data;  
       
       
         generating a current code book, having a different association of code words and symbol data as compared to a previously generated code book, in accordance with said adapted association information; and  
       
       
         decoding said received code word data using said current code book and outputting decoded data. 
       
     
     
       50. The variable- length decoding method as claimed in    claim 49   , wherein the code words of said current code book and said previously generated code book are identical.   
     
     
       51. The variable- length decoding method as claimed in    claim 50   , wherein said generating a current code book is carried out at a pre - determined interval.   
     
     
       52. The variable- length decoding method as claimed in    claim 51   , wherein said predetermined interval is for one slice of video data.   
     
     
       53. The variable- length decoding method as claimed in    claim 51   , wherein said predetermined interval is for one frame of video data.   
     
     
       54. The variable- length decoding method as claimed in    claim 51   , wherein said predetermined interval is for one field of video data.   
     
     
       55. A variable- length encoding method, comprising:    
       
         receiving input symbol data;  
       
         adapting a relationship between each distinct received input symbol data and variable - length code words and generating adapted association information for each distinct received input symbol data, wherein the adapted association information for a code word is received only when the code word data is received for the first time during a predetermined time interval and before another code word data is received;    
       
         encoding said received input symbol data using a current code book, having a different association of code words and symbol data as compared to a previously used code book, in accordance with said adapted association information, to generate variable length code words; and  
       
       
         transmitting said adapted association information and said variable length code words in an alternating manner. 
       
     
     
       56. The variable- length encoding method as claimed in    claim 55   , wherein the code words of said current code book and said previously used code book are identical.   
     
     
       57. The variable- length encoding method as claimed in    claim 56   , wherein said encoding said received input symbol data using said current code book is carried out at a pre - determined interval.   
     
     
       58. The variable- length encoding method as claimed in    claim 57   , wherein said predetermined interval is for one slice of video data.   
     
     
       59. The variable- length encoding method as claimed in    claim 57   , wherein said predetermined interval is for one frame of video data.   
     
     
       60. The variable- length encoding method as claimed in    claim 57   , wherein said predetermined interval is for one field of video data.   
     
     
       61. A variable- length decoding method, comprising:    
       
         receiving interleaved adapted association information and code word data;  
       
       
         decoding said received code word using a code book, having a different association of code words and symbol data as compared to a previously used code book, in accordance with said adapted association indication information; and  
       
       
         outputting said decoded code word data. 
       
     
     
       62. The variable- length decoding method as claimed in    claim 61   , wherein the code words of said current code book and said previously used code book are identical.   
     
     
       63. The variable- length decoding method as claimed in    claim 62   , wherein said decoding said received code words comprises generating a current code book based on said adapted indication information during a pre - determined interval.   
     
     
       64. The variable- length decoding method as claimed in    claim 63   , wherein said predetermined interval is for one slice of video data.   
     
     
       65. The variable- length decoding method as claimed in    claim 63   , wherein said predetermined interval is for one frame of video data.   
     
     
       66. The variable- length decoding method as claimed in    claim 63   , wherein said predetermined interval is for one field of video data.