JP2006324944A - Encoder - Google Patents

Abstract

An encoding apparatus suitable for Huffman encoding capable of achieving high-speed encoding processing and maintaining high compression efficiency is provided.
A table creation unit (2) includes an occurrence probability calculation circuit (21) and a maximum value detection / code allocation module (22), and is performed in parallel with an encoding process using an encoding table (13a) or (13b) by an encoding processing unit (1). Thus, an update coding table is created. The occurrence probability calculation circuit 21 counts the number of appearances for each piece of code data based on the encoding process information S1a provided from the CAM 11 of the encoding processing unit 1, thereby generating the occurrence probability for the latest pre-encoding data D0. I do. Furthermore, when the compression efficiency falls below a preset threshold value, the table creation unit 2 controls exchange processing between the encoding table to be used and the update encoding table between the encoding tables 13a and 13b.
[Selection] Figure 2

Description

  Huffman coding is one of the mainstream methods for data compression, and JPEG and MPEG standardized by ISO for multimedia such as audio, image and video, and ZIP which is the standard for file compression format. It is an effective lossless compression method widely implemented in software and hardware such as LHA.

  Specifically, in JPEG and MPEG, it is used to compress the total amount of data after deleting redundant data of pixels. In LHA, Huffman coding is used to compress similar character strings existing in data. It is used. As a Huffman encoder and an image processing apparatus that perform Huffman encoding processing, for example, there are an encoding apparatus disclosed in Patent Document 1 and an image processing apparatus disclosed in Patent Document 2.

JP-A-8-51370 JP 2005-12495 A

  In general Huffman coding algorithm, it is necessary to create an appearance frequency table (coding table) used for coding. Therefore, it is necessary to scan all pre-coding data once before compression, and then perform compression. It is structured. Therefore, online compression is difficult.

  In order to omit the process of checking the appearance frequency, a method using an existing coding table and a method of sending a mixture of uncoded data and coded data each time by improving the algorithm have been proposed. However, in these methods, in the former case, compression is not possible when there is no existing coding table, and in the latter case, compression efficiency (ratio of data amount of post-encoding data to pre-encoding data). There are problems such as worsening and complicated implementation. Therefore, there is a problem that it is difficult to apply Huffman coding to various applications or to implement it in a compact manner. Hereinafter, these problems will be described in detail.

(Problems of static Huffman coding)
Static Huffman coding is the most widely implemented form. Based on the appearing symbol string, an encoding table is first created, and compression is again performed using the encoding table created for the similar symbol string. However, in this method, since it is necessary to scan data twice in order to perform compression, online real-time compression becomes difficult.

  Therefore, in practice, it is rare that an encoding table is created each time, and an existing table created based on standard data is often prepared and encoded. Microprocessor-based, SRAM-based, PLA (Programmable Logic Array) -based, and CAM (Content Addresable Memory) -based architectures have been proposed for methods using this existing table (called "static table") . Since the microprocessor-based architecture is encoded by software, the processing efficiency is low compared to hardware. In the SRAM-based architecture, several clock cycles are required to calculate an address for finding conversion data from the encoding table when encoding. The PLA-based architecture tends to increase the amount of hardware as the size of the encoding table increases. In addition, the conventional CAM-based architecture simply performs a matching search function using a coding table, so it is fast but lacks flexibility.

  All of these implementation methods use existing coding tables based on standard data, so in the case of content such as moving images where the tendency of the image changes rapidly, compression efficiency may decrease. Furthermore, there is a problem that it cannot be applied to an application in which an existing encoding table does not exist.

(Problems of adaptive Huffman coding)
Adaptive Huffman coding has been considered to improve on-line compression, which is a problem of static Huffman coding, and compression according to an arbitrary symbol string for which no existing table exists.

  The feature is that each time a symbol is processed, the Huffman tree is updated, and encoding is performed using the tree constructed at that time. That is, since encoding is not performed by looking at the entire symbol string before encoding, online processing is possible, and it is not necessary to create an encoding table.

  However, there are also some problems with compression efficiency and real-time properties. In other words, because of the characteristics of the algorithm, since the first appearance symbol must be sent without being encoded in addition to the encoded data, the amount of data increases accordingly.

  Furthermore, due to the locality of data, even if a short code is assigned to a symbol that appears intensively, if it does not appear thereafter, the compression efficiency may be lower than that of static Huffman coding as the amount of data increases. There is a problem.

  For this, a technique of periodically refreshing the coding table may be used. However, discarding the past occurrence probability of data also deteriorates the compression efficiency.

  Further, since the Huffman tree is updated every time encoding is performed, more time is required for processing. Even if online processing is possible, this may not be applicable to real-time applications.

  Research on improving the algorithm to improve the Huffman tree update processing time and research on speeding up using CAM to update the tree have been conducted, but it is difficult to implement adaptive Huffman coding in hardware. There was a problem that there were few merits compared with the compression effect.

  The present invention has been made to solve the above-described problems, and an object of the present invention is to obtain an encoding apparatus suitable for Huffman encoding capable of achieving high speed encoding processing and maintaining high compression efficiency. And

  The encoding apparatus according to claim 1 of the present invention receives pre-encoding data, encodes the pre-encoding data using a use target encoding table, generates post-encoding data, and An encoding processing unit that outputs encoding processing information including the appearance status of the pre-encoding data, and the pre-encoding data based on the encoding processing information in parallel with the encoding processing by the encoding processing unit A table creation unit that creates an update encoding table based on the calculation result, and the table creation unit, when the compression efficiency in the encoding process does not satisfy a predetermined criterion, The use target coding table is replaced with the update coding table.

  According to the first aspect of the present invention, the table creation unit of the coding apparatus creates the update coding table in parallel with the coding process by the coding processing unit, and therefore hinders the high speed of the coding process. Therefore, an update encoding table based on the latest pre-encoding data can be created.

  Furthermore, since the table creation unit replaces the use target coding table with the update coding table when the compression efficiency in the coding process does not satisfy a predetermined standard, it is possible to always maintain a high compression efficiency.

<Overview of CAM>
The encoding apparatus according to the present invention has a Huffman encoding architecture using CAM (Content Addressable Memory). First, a general outline of CAM will be described.

  FIG. 18 is an explanatory diagram showing the concept of CAM. CAM is a kind of functional memory called associative memory. A memory such as a general RAM (Random Access Memory) shown in FIG. 18 (a) refers to each data stored using an address, whereas a CAM is shown in FIG. 18 (b). The CAM has a function of outputting a comparison result (a match signal and a storage address of the matched data) with the comparison data based on the contents of the stored data, so that each stored data can be referred to. , “Content addressing memory”.

  For this reason, when storing data inside a normal memory, an address, which is a unique number, is added to each memory. Therefore, if an address is input, the stored data can be output accordingly. Therefore, when searching for data that matches certain comparison data in the RAM, it is necessary to input addresses in order and to check the data stored there in order.

  On the other hand, when comparison data serving as search data is input to reference (comparison) data stored in an internal memory area, the CAM transfers all reference data to a constant clock by an internal comparator. All the matches are searched in a cycle, and if there is a match, a match signal can be output for the corresponding data. It is also possible to output the address of the reference data that coincides at the same time. As another function, it is also possible to search for a specific bit only using a mask.

  Since the CAM matching search is essentially performed in parallel, it has an advantage that the search result can be obtained very quickly and efficiently as the number of reference data in the memory increases as compared with a normal RAM. .

<Basic configuration>
FIG. 1 is a block diagram showing an outline of the internal configuration of an encoding apparatus having a CAM-based Huffman encoding architecture according to the present invention. In the figure, the encoding processing unit 1 internally uses a target encoding table (not shown in FIG. 1) used for current encoding and an update encoding table (not shown in FIG. 1) to be replaced next. It is assumed that they have at least.

  As shown in the figure, the encoding processing unit 1 inputs pre-encoding data D0, and uses post-encoding data D1 obtained by Huffman encoding the pre-encoding data D0 using an internal use target encoding table. While outputting to the output process part 3, the encoding process information S1 containing the appearance information of the pre-encoding data D0 obtained simultaneously is output to the table preparation part 2. FIG. The output processing unit 3 outputs output data D3 based on the encoded data D1.

  The table creation unit 2 performs the occurrence probability calculation process of the pre-encoding data D0 based on the encoding process information S1 in parallel with the encoding process of the encoding processing unit 1, and updates the Huffman tree based on the calculation result Then, the update coding table is updated. The contents of the update process are appropriately given to the encoding processing unit 1 as table update information S2.

  Then, if the compression efficiency does not satisfy the predetermined standard, the table creation unit 2 determines that there is a need to change the coding table, and gives a coding table update command (not shown) to the coding processing unit 1 for coding. The use target coding table in the processing unit 1 is replaced with the update coding table.

<(Sequential encoding method)>
Depending on the application, it can be considered that the data before encoding is sequentially sent one after another. A coding apparatus according to the first embodiment having a CAM-based coding architecture that employs a sequential coding scheme is provided for such an application.

  FIG. 2 is an explanatory diagram showing the overall configuration of the encoding apparatus according to the first embodiment. As shown in the figure, the encoding processing unit 1 for taking in the pre-encoding data D0 includes a CAM 11, a switch 17, and encoding tables 13a and 13b (RAM 13).

  The CAM 11 in the encoding processing unit 1 sequentially fetches the pre-encoding data D0 sent sequentially as comparison data, and executes a matching search process. Since all patterns of pre-encoding data are stored as reference data in the CAM 11 so as to correspond to the encoding tables 13a and 13b (RAM 13), a match signal that indicates the match with the comparison data obtained from the search result is displayed. A match detection result signal S11 including an address (match signal address) can be output to the switch 17.

  Further, the encoding processing unit 1 outputs the encoding processing information S1a obtained during the matching search process to the table creating unit 2.

  Also, the encoding processing unit 1 has two encoding tables 13a and 13b therein, and one of the encoding tables 13a and 13b becomes a use target encoding table by the switch 17, and the other is an update code. Selected as the conversion table. Therefore, the coincidence detection result signal S11 is selectively output by the switch 17 to the table that is the use target coding table among the coding tables 13a and 13b.

  The table creation unit 2 is a processing unit that creates an update coding table in parallel with the coding process using the coding table 13a or 13b by the coding processing unit 1. The table creation unit 2 includes an occurrence probability calculation circuit 21 and a maximum value detection / code allocation module 22 inside.

  The occurrence probability calculation circuit 21 counts the number of appearances for each piece of code data based on the encoding process information S1a provided from the CAM 11 of the encoding processing unit 1, thereby generating the occurrence probability for the latest pre-encoding data D0. I do. Then, the occurrence probability calculation processing result calculated by the occurrence probability calculation circuit 21 is input to the maximum value detection / code allocation module 22.

  The maximum value detection / code allocation module 22 determines whether the number of appearances for each code data is a predetermined setting value, the maximum value (MAX) that can be counted, or when the compression efficiency falls below a threshold value. Then, Huffman codes with shorter bit lengths are assigned in order from the highest frequency, and code table creation data S22 for creating a new update coding table is created.

  The update coding table creation processing by the table creation unit 2 is executed in parallel with the coding processing by the coding processing unit 1, and is based on the appearance frequency of the latest pre-coding data D0. The code table creation data S22 for creation is obtained.

  Furthermore, when the compression efficiency falls below a preset threshold value, the table creation unit 2 controls exchange processing between the encoding table to be used and the update encoding table between the encoding tables 13a and 13b. For example, when the target encoding table is the encoding table 13a and the update encoding table is the encoding table 13b, the target encoding table is the encoding table 13b, and the update encoding table is the encoding table 13a. A command for replacement is given to the switch 17. As a result, the encoding processing unit 1 can always maintain a high compression efficiency without the compression efficiency falling below the threshold value.

  Whether the compression efficiency by the table creation unit 2 is below the threshold value can be determined by, for example, determining by logic that the count value of pre-code data having a long code length has increased.

  The encoded data D1 output from the encoding tables 13a and 13b is taken into the output processing unit 3. The output processing unit 3 includes a shifter 31, buffers 32a and 32b, and a switch 33 therein, and buffers the encoded data D1 by the shifter 31 and the buffers 32a and 32b and outputs it as output data D3. .

  FIG. 3 is an explanatory diagram showing a detailed configuration of the encoding apparatus according to the first embodiment. As shown in the figure, the CAM 11 includes an address decoder 14, a comparison register RC, a mask register RM, a reference data storage area RG1, a search result storage register R1, which is a first search result storage register, a priority encoder 15, a match signal, The address generation circuit 16 is configured. The switch 17 is composed of selectors 17a and 17b, and a selector 18 is provided at the subsequent stage of the encoding tables 13a and 13b.

  The comparison register RC takes in the pre-encoding data D0, and the mask register RM stores mask data indicating the bits to be masked. In the reference data storage area RG1, all patterns of pre-encoding data indicating symbols and the like are stored as reference data DR1 to DRn.

  The address decoder 14 decodes the read / write address Ad to determine a selection address, accesses the reference data DRi corresponding to the selection address i (i = 1 to n) from the encoding processing unit 1, and reads the reference data DR at the time of reading. Can be output as The search result storage register R1 is a register that stores the search result bits DB1 to DBn corresponding to the reference data DR1 to DRn stored in the reference data storage area RG1. The search result storage register R1 is connected to the priority encoder 15 so that the internal search result bits DB1 to DBn can be read.

  Based on the information of the search result bits DB1 to DBn, the priority encoder 15 outputs the address corresponding to the match search result bit DBi in the set state (stored “1”) to the match signal and address generation circuit 16 as a match signal address. The match signal and address generation circuit 16 outputs a match signal S11a indicating that the search results match and a match address signal S11b indicating the match signal address to the selectors 17a and 17b.

  In the active state, the selectors 17a and 17b provide enable signals ENa and ENb for instructing activation / inactivation, write signals WRa and WRb for instructing writing / reading, and a selection address signal for instructing a selection address. SAa and SAb, and code data DHa and DHb indicating write data are output. The activation / inactivation of the selectors 17a and 17b is controlled by a control signal S25 from the control circuit 23.

  The encoding tables 13a and 13b output read data D13a and D13b to the selector 18 based on the various signals described above from the selectors 17a and 17b. Based on the control signal S32 from the control circuit 23, the selector 18 outputs one of the read data D13a and D13b as the encoded data D1.

  The occurrence probability calculation circuit 21 has counters CT1 to CTn inside, and these counters CT1 to CTn are provided corresponding to the search result bits DB1 to DBn of the search result storage register R1, and the corresponding search result bits DB match. Each time the search result bit DBi becomes “1” (set state), the count is incremented. Therefore, the search result bits DB1 to DBn become the encoding process information S1a of FIG.

  The maximum value detection / code assignment module 22 assigns a Huffman code in order from an address corresponding to the counter CT having a large count value, based on the occurrence probability calculation results that are the count values of the counters CT1 to CTn. A code address signal S22a and a code data signal S22b for creating a new conversion table are output to the selectors 17a and 17b.

  The control circuit 23 receives the encoded data D1, the threshold data D21, and the set value data D22, and also receives the control signal S22c from the maximum value detection / code allocation module 22, and based on these signals, the maximum value detection / code allocation module 22, the information transmission signal S23, the control signal S24 to the priority encoder 15, the control signal S25 to the selectors 17a and 17b, and the control signal S32 to the selector 20 are given. The information transmission signal S23 includes information such as threshold data D21, set value data D22, and encoded data D1.

  The selectors 17a and 17b function based on the control signal S25, one functions for encoding processing based on the coincidence signal and the coincidence signal S11a and the coincidence address signal S11b from the address generation circuit 16, and the other functions as the maximum value detection / code allocation module 22. Functions for an encoding table update process based on the encoding address signal S22a and the encoding data signal S22a.

  FIG. 4 is a flowchart showing an encoding process and an encoding table creation process in the encoding apparatus according to the first embodiment. Hereinafter, the operation of the first embodiment will be described in detail with reference to FIG. For convenience of explanation, it is assumed that the current use target encoding table is the encoding table 13a and the update encoding table is the encoding table 13b. In the processing described in FIG. 4, overall control is performed by the control circuit 23, and individual operations are executed by the encoding processing unit 1, the table creation unit 2, and the output processing unit 3, respectively. In FIG. 4, the execution of each of the constituent units 1 to 3 is classified for convenience, but other constituent units may actually perform.

  In step ST1 of FIG. 4, pre-encoding data D0 is sequentially input. The pre-encoding data D0 is taken into the comparison register RC of CAM11. In the example of FIG. 3, “000... 001” that is the pre-encoding data D0 is stored as the comparison data DC in the comparison register RC, and the mask register RM stores all “0” mask data that is not masked. The case where it is set is shown.

  Next, in step ST2, the selectors 17a and 17b satisfy “compression efficiency ≦ threshold” via the control signal S22c from the maximum value detection / code allocation module 22 and the control signal S25 from the control circuit 23 ( (YES), whether or not (NO) is recognized. If YES, the process proceeds to step ST3. If NO, the encoding table exchange process (encoding table 13a, which is the encoding table to be used, and update) is updated in step ST7. After replacing the encoding table 13b which is the encoding table), the process proceeds to step ST3.

  In step ST3, a match search between the pre-encoding data D0 and the reference data DR1 to DRn in the reference data storage area RG1 is performed in the CAM 11. In the match search, any of the reference data in the reference data storage area RG1 and the pre-encoding data D0 always match and correspond to the matched reference data (matched reference data DRi (i = 1 to n)). The match search result bit DBi of the search result storage register R1 is set to “1” (set state). In FIG. 3, the search result bit DB corresponding to the comparison data DC “000... 001” is set to “1”.

  Thereafter, in step ST4, transmission processing to the coincidence signal address to the encoding table 13a is performed. Hereinafter, this process will be described in detail.

  As described above, the priority encoder 15 outputs the address corresponding to the match search result bit DBi to the match signal and address generation circuit 16 as the match signal address based on the information of the search result bits DB1 to DBn in the search result storage register R1. To do. The match signal and address generation circuit 16 outputs a match signal S11a indicating that the search results match and a match address signal S11b indicating the match signal address to the selectors 17a and 17b.

  At this time, since the selector 17a corresponding to the encoding table 13a is enabled by the control signal S25, the selector 17a sets the enable signal ENa in the active state and the write signal WRa in the inactive state (read state), and matches. Based on the signal S11a and the coincidence address signal S11b, a selection address signal SAa for instructing the coincidence signal address is output to the encoding table 13a.

  As a result, in step ST5, the encoding processing unit 1 refers to the encoding table 13a and outputs the code data stored at the address indicated by the selection address signal SAa to the selector 18 as read data D13a. The selector 18 outputs the read data D13a as the encoded data D1 in accordance with the control signal S32 from the control circuit 23.

  In step S6, output data D3 is finally output from the output processing unit 3. In other words, the output processing unit 3 outputs the encoded data D1 to one of the buffers 32a and 32b by the shifter 31, and when it becomes full, switches the output destination to the other buffer. During this time, the output destination is full under the control of the switch 33. Output as output data D3 from one of the buffers in the state.

  FIG. 5 is a conceptual diagram showing the relationship between the CAM 11 and the RAM 13 in the process of step ST5. For convenience of explanation, the addresses of the CAM 11 and the RAM 13 are indicated by 2 bits, the reference data stored by the CAM 11 and the code data stored by the RAM 13 are respectively indicated by 3 bits.

  As shown in FIG. 5, when “111” is input as the pre-encoding data D0, it matches “111” in the reference data storage area RG1 of the CAM 11, and this “111” is set to “10” of the address 35. Equivalent to. In the configuration of FIG. 3, the address encoded by the priority encoder 15 is “10” for the bit storing “1” among the search result bits DB1 to DBn. A signal defining this address “10” becomes the coincidence address signal S11b.

  The RAM 13 (encoding tables 13a and 13b) that has received the match address signal S11b, based on the match address signal S11b, from the data in the stored code data 37, data “010” corresponding to “10” in the code data address 36. The data “010” is output as encoded data D1.

  Thus, the encoded data D1 can be obtained at high speed by the cooperation between the CAM 11 and the RAM 13 based on the coincidence address signal S11b.

  FIG. 6 is an explanatory diagram showing a connection example between the CAM 11 and the RAM 13. As shown in the figure, the coincidence signal lines CL1 to CLn of the CAM 11 and the word lines WL1 to WLn of the RAM 13 are connected by a connecting portion 49.

  The coincidence signal lines CL1 to CLn of the CAM 11 are provided corresponding to the reference data DR1 to DRn, a memory cell MC11 having a predetermined number of bits is provided corresponding to each of the reference data DR1 to DRn, and a comparator is provided for each memory cell MC11. CP1 to CPn (corresponding to reference data DR1 to DRn) are provided.

  On the other hand, word lines WL1 to WLn of RAM 13 are provided corresponding to code data DH1 to DHn, and memory cells MC13 having a predetermined number of bits are provided corresponding to code data DH1 to DHn.

  In the CAM 11 and the RAM 13 having such a connection relationship, only the coincidence signal line CLi corresponding to the coincidence reference data DRi (i = 1 to n) is set in an active state by the comparator CPi having a predetermined number of bits.

  As a result, only the word line WLi connected to the coincidence signal line CLi is activated, and the code data DHi which is the storage data of the memory cell MC13 connected to the word line WLi is read as the read data D13.

  In this way, the coincidence signal lines CL1 to CLn of the CAM 11 and the word lines WL1 to WLn of the RAM 13 are connected by the connection unit 49, thereby setting the address 35 of the CAM 11 and the code data address 36 of the RAM 13 shown in FIG. Since it can be made unnecessary, it is possible to accumulate in a smaller area.

  3 and 4, the table creation unit 2 performs a process of counting the number of matches for each of the reference data DR1 to DRn in step ST8 in parallel with the match search process of step ST3 by the encoding process unit 1. Do. Hereinafter, the details of this process will be described.

  The counters CT1 to CTn in the occurrence probability calculation circuit 21 count up each time the corresponding search result bits DB1 to DBn become “1”. Therefore, in the pre-encoding data D0 input sequentially, the number of matches of the search result bits DB1 to DBn, that is, the reference data DR1 to DRn is counted by the counters CT1 to CTn.

  In step ST9, whether any of the count values of the counters CT1 to CTn reaches a set value (specified by the set value data D22) (YES) or not (NO), and in step ST10, any of the counters CT1 to CTn is set. Whether the countable maximum value (MAX) is reached (YES) or not (NO), and whether or not the compression efficiency is below a threshold value (specified by threshold data D21) (YES) or not (NO) is checked in step ST11. Is done.

  If YES in step ST9, YES in ST10, or NO in step ST11, the process proceeds to step ST12.

  In step ST12, the maximum value detection / sign assignment module 22 updates the Huffman code in order from the address (pre-code data) corresponding to the counter CT having a large count value, based on the count values of the counters CT1 to CTn. A new encoding table using a Huffman code necessary for the encoding table is created.

  Then, the process proceeds to step ST13, where the code address signal S22a for defining the address based on the new coding table created in step ST12 and the code data signal S22a for defining the code data corresponding to the address are selected by the selectors 17a, By outputting to 17b, a coding table update process is executed.

  Since the current update coding table is the coding table 13b, under the control of the control signal S25, the selector 17b uses the enable signal ENb for instructing the active state, the write signal WRb for instructing writing, and the address signal for coding. By sequentially outputting the selection address signal SAb indicating the address defined by S22a and the code data DHb indicating the code data defined by the code data signal S22a to the coding table 13b, the coding table 13b Update the contents.

  Thereafter, the process proceeds to step ST7. When the cause of execution of step ST12 is NO in step ST11 (when the compression efficiency is lower than the threshold value), the encoding table to be used is changed from the encoding table 13a to the encoding table 13b. Switch to. In addition, when step ST7 is performed after step ST13, it complete | finishes at step ST7 and does not transfer to step ST2. The process proceeds to step ST2 only when NO is determined in step ST1 and step ST7 is subsequently executed.

  As described above, in the encoding apparatus according to the first embodiment, in order to maintain the compression efficiency while the encoding processing unit 1 encodes the pre-encoding data D0 that is sequentially input in real time. Thus, it is possible to always prepare an optimal update coding table by the table creation unit 2.

  The occurrence probability calculation circuit 21 of the table creation unit 2 can recognize the appearance information of the latest pre-encoding data D0 accurately and at high speed based on the contents of the search result bits DB1 to DBn in the search result storage register R1. It is possible to perform an occurrence probability calculation process.

  As a result, coding suitable for Huffman coding that solves the problems of static Huffman coding and adaptive Huffman coding, achieves high-speed Huffman coding processing, and maintains high compression efficiency. A device can be obtained.

<Embodiment 2 (Storage Coding System)>
CAM-based encoding using a storage encoding method is provided for applications in which data before encoding is stored in a memory or the like in advance or encoding processing is performed after the data is stored. 4 is an encoding apparatus according to a second embodiment having an architecture.

  FIG. 7 is an explanatory diagram showing the overall configuration of the encoding apparatus according to the second embodiment. As shown in the figure, the encoding processing unit 5 for taking in the pre-encoding data D0 has a CAM 19, a switch 17, and encoding tables 13a and 13b (RAM 13).

  After the CAM 19 in the encoding processing unit 5 takes in the pre-encoding data D0 that is sequentially input into the pre-encoding data storage area RG2 (see FIG. 8 described later) as a predetermined number of stored data. Execute the matching search process in a batch. Similar to the CAM 11 of the first embodiment, the CAM 19 stores all patterns of pre-encoding data in the reference data storage area RG1 so as to correspond to the encoding tables 13a and 13b. The coincidence detection result signal S19 including the coincidence signal address (coincidence signal address) instructing coincidence with the data is output to the switch 17.

  Further, the encoding processing unit 5 outputs the encoding processing information S1b obtained during the matching search process to the table creating unit 6.

  Also, the encoding processing unit 5 has two encoding tables 13a and 13b therein, and one of the encoding tables 13a and 13b becomes a use target encoding table by the switch 17, and the other is an update code. Selected as the conversion table. Therefore, the coincidence detection result signal S19 is selectively output by the switch 17 to the table that is the use target coding table among the coding tables 13a and 13b.

  The CAM 19 and the RAM 13 (encoding tables 13a and 13b) are configured so that the coincidence signal line of the CAM 19 and the word line of the RAM 13 are connected via the switch 17 as in the example of FIG. Therefore, the integration degree can be improved.

  The encoded data D1 output from the encoding tables 13a and 13b is taken into the output processing unit 3. The output processing unit 3 outputs the encoded data D1 to one of the buffers 32a and 32b by the shifter 31, and when it becomes full, switches the output destination to the other buffer. During this time, the full state is controlled under the control of the switch 33. The data is output as output data D3 from the one buffer.

  The table creation unit 6 is a processing unit that creates an update coding table in parallel with the processing of the coding processing unit 5, similarly to the table creation unit 2 of the first embodiment. The table creation unit 6 includes an occurrence probability calculation circuit 24 and a maximum value detection / code assignment module 22 therein.

  Further, as with the table creation unit 2 of the first embodiment, the table creation unit 6 updates the target coding table between the coding tables 13a and 13b when the compression efficiency falls below a preset threshold value. Exchange processing control with the encoding table is performed.

  The occurrence probability calculation circuit 24 in the table creation unit 6 stores the data stored in the pre-encoding data storage area RG2 (see FIG. 8 described later) based on the encoding processing information S1b provided from the CAM 19 of the encoding processing unit 5. An occurrence probability calculation process of the pre-encoding data D0) is performed. The occurrence probability calculation result of the occurrence probability calculation circuit 24 is input to the maximum value detection / sign assignment module 22.

  Based on the occurrence probability calculation result, the maximum value detection / code allocation module 22 recognizes the number of appearances (corresponding number) of the address unit (corresponding to the content of the pre-encoding data) and sets the number of appearances determined in advance. When the maximum countable value (MAX) is reached, or the compression efficiency falls below the threshold value, Huffman codes with shorter bit lengths are assigned in order from the highest frequency to the new update Create an encoding table.

  The new coding table creation processing by the table creation unit 6 is executed in parallel with the coding processing by the coding processing unit 5.

  The reference data rewrite processing unit 4 has a feedback circuit 41 therein, receives the encoded data D1, gives a rewrite control signal S41 to the CAM 19, and stores the pre-encoding data storage area RG2 of the CAM 19 (see FIG. 8 shown later). When a plurality of pre-encoding data D0 are stored in the storage unit, rewrite processing for rewriting all of the pre-encoding data D1 to the post-encoding data D1 is performed on the storage data in the pre-encoding data storage area RG2 (see FIG. 8 described later). Do.

  FIG. 8 is an explanatory diagram showing a detailed configuration of the encoding apparatus according to the second embodiment. As shown in the figure, the CAM 19 includes an address decoder 14, a comparison register RC, a mask register RM, a reference data storage area RG1, a pre-encoding data storage area RG2, a search result storage register R1, and a second search result storage register. A search result storage register R2, a flag bit storage register R4, and a coincidence signal and address generation circuit 16 are included. The switch 17 is composed of selectors 17a and 17b, and a selector 20 is provided after the encoding tables 13a and 13b.

  The comparison register RC takes in the pre-encoding data stored in the pre-encoding data storage area RG2 selected by the address decoder 14, and the mask register RM stores the mask data indicating the bit to be masked. To do. In the reference data storage area RG1, all patterns of pre-encoding data are stored as reference data DR1 to DRn.

  The address decoder 14 decodes the read / write address Ad to determine a code processing selection address for the reference data storage area RG1 or the pre-encoding data storage area RG2. During the encoding process, the CAM 19 sequentially outputs the pre-encoding data stored in the pre-encoding data storage area RG2 to the comparison register RC, and the comparison data DC of the comparison register RC and the reference data DR1 in the reference data storage area RG1. A match search process with -DRn is performed, and all the stored data in the pre-encoding data storage area RG2 that matches the comparison data DC are rewritten to the encoded data D1 during the rewriting process.

  The search result storage register R1 is a register that stores search result bits DB1 to DBn, which are first search result bits, corresponding to the reference data DR1 to DRn stored in the reference data storage area RG1. The search result storage register R1 is connected to the match signal and address generation circuit 16 so that the internal search result bits DB1 to DBn can be read.

  The search result storage register R2 is a detection result which is a second search result bit corresponding to the storage data DS1 to DSm stored in the pre-encoding data storage area RG2 (assuming that m can be stored corresponding to the address). It is a register for storing bits CD1 to CDm. The search result storage register R2 is connected to the occurrence probability calculation circuit 24 so that the internal detection result bits CD1 to CDm can be read.

  Based on the information of the search result bits DB1 to DBn, the match signal and address generation circuit 16 uses the address corresponding to the match search result bit DBi as a match signal address, and a match signal S11a indicating that the search results match, and a match signal address Is output to the selectors 17a and 17b.

  The selectors 17a and 17b provide the encoding tables 13a and 13b with enable signals ENa and ENb for instructing activation / inactivation, write signals WRa and WRb for instructing writing / reading, and selection address signals SAa and SAb for instructing selection addresses. The code data DHa and DHb for instructing write data are output. The activation / inactivation of the selectors 17a and 17b is controlled by a control signal S25 from the control circuit 25.

  The encoding tables 13a and 13b output read data D13a and D13b to the selector 20 based on various signals from the selectors 17a and 17b. Based on the control signal S32 from the control circuit 25, the selector 20 outputs one of the read data D13a and D13b as the encoded data D1.

  The occurrence probability calculation circuit 24 matches the reference data (pre-encoding data) indicated by the match address signal S11b among the reference data DR1 to DRn based on the detection result bits CD1 to CDm and the match address signal S11b of the search result storage register R2. An occurrence probability calculation process for counting the number of times (number of appearances) is performed. Therefore, the encoding process information S1b is the detection result bits CD1 to CDm and the coincidence address signal S11b. Note that the comparison data DC, the stored data DS in the set state, or the like may be fetched instead of the coincidence address signal S11b.

  The maximum value detection / code assignment module 22 assigns a Huffman code in order from the address (pre-code data) corresponding to the counter CT having a large count value based on the occurrence probability calculation result obtained from the occurrence probability calculation circuit 24. A new update coding table is created using codes, and the code address signal S22a and code data signal S22b for creating the update coding table are output to the selectors 17a and 17b.

  The control circuit 25 receives the encoded data D1, the threshold data D21, and the set value data D22, and also receives the control signal S22c from the maximum value detection / code allocation module 22, and based on these signals, the maximum value detection / code allocation module 22, the information transmission signal S 23, the control signals S 25 to the selectors 17 a and 17 b, the control signal S 32 to the selector 20, the control signal S 20 to the occurrence probability calculation circuit 24, and the flag bit storage register R 4 and the occurrence probability calculation circuit 24 to reset. Signal S26 is provided. The information transmission signal S23 includes information such as threshold data D21, set value data D22, and encoded data D1.

  Further, it functions as a feedback circuit 41 in the reference data rewrite processing unit 4 together with the control circuit 25 and the signal line 50 through which the encoded data D1 is fed back to the CAM 19, and gives a rewrite control signal S41 instructing rewrite to the CAM 19, When there are a plurality of storage data DS having the same value as the comparison data DC in the comparison register RC in the pre-encoding data storage area RG2, a rewrite process is executed to replace the stored data with the encoded data D1.

  The selectors 17a and 17b function based on the control signal S25, one functions for encoding processing based on the coincidence signal and the coincidence signal S11a and the coincidence address signal S11b from the address generation circuit 16, and the other functions as the maximum value detection / code allocation module 22. Functions for an encoding table update process based on the encoding address signal S22a and the encoding data signal S22b.

  FIG. 9 is a flowchart showing an encoding process and an encoding table creation process in the encoding apparatus according to the second embodiment. Hereinafter, the operation of the second embodiment will be described in detail with reference to FIG. For convenience of explanation, it is assumed that the current use target encoding table is the encoding table 13a and the update encoding table is the encoding table 13b. 9, the overall control is performed by the control circuit 25, and each operation is executed by the encoding processing unit 5, the table creation unit 6, the output processing unit 3, and the reference data rewrite processing unit 4, respectively. Is done. In FIG. 9, the execution of each of the components 3 to 6 is classified for convenience, but other components may actually be performed in practice.

  In step ST21 in FIG. 9, pre-encoding data D0 is sequentially fetched, and data set processing is performed for storing the storage data DS1 to DSm in association with addresses in the pre-encoding data storage area RG2.

  Next, in step ST22, the selectors 17a and 17b satisfy “compression efficiency ≦ threshold” via the control signal S22c from the maximum value detection / code allocation module 22 and the control signal S25 from the control circuit 25 ( YES or NO (NO). If YES, the process proceeds to step ST23. If NO, the encoding table exchange process (the encoding table to be used encodes the encoding table 13a) in step ST32. After performing the process of changing to the table 13b, the process proceeds to step ST23.

  In step ST23, the CAM 19 is set to the data read mode from the pre-encoding data storage area RG2 based on the read / write address Ad, and then the address of the read / write address Ad is set to the initial value “0”.

  In step ST24, it is checked whether the bit in the flag bit storage register R4 corresponding to the read / write address Ad (= “0”) is “1” (YES) or not (NO). For example, it is determined that the data is not replaced with the encoded data D1, and the process proceeds to step ST25.

  In step ST25, the storage data DS in the pre-encoding data storage area RG2 designated by the read / write address Ad in the CAM 19 is read as the comparison data DC of the comparison register RC, and the comparison data DC and the reference data storage area RG1 are read. A match search with reference data DR1 to DRn is performed.

  In the match search, any of the reference data in the reference data storage area RG1 and the comparison data DC always match, and the search result corresponding to the matched reference data (matched reference data DRi (any of i = 1 to n)). The match search result bit DBi of the storage register R1 is set to “1” (set state). In FIG. 8, the search result bit (DB) in the search result storage register R1 corresponding to the comparison data DC “000... 001” is set to “1”.

  At the same time, there is at least one “000... 001” in the pre-encoding data storage area RG2, and all the search result bits CD corresponding to the stored data DS in the search result storage register R2 corresponding to “000. Set to “1” (set state). In the example of FIG. 8, two identical data indicating “000... 001” are stored as the stored data DS in the pre-encoding data storage area RG2, and the search result storage register R2 is set to “1” at two locations. An example is shown.

  Thereafter, in step ST26, as in step ST4 of the first embodiment, transmission processing to the coincidence signal address to the encoding table 13a is performed.

  Thereafter, in step ST31, referring to the encoding table 13a, the encoded data stored at the address indicated by the selection address signal SAa is output to the selector 20 as read data D13a, and the selector 20 is controlled by the control circuit 25. In accordance with the signal S32, the read data D13a is output as the encoded data D1. Finally, output data D3 is output from the output processing unit 3.

  Further, in step ST30 after step ST26, rewriting processing by the control circuit 25 and the signal line 50 functioning as the feedback circuit 41 is executed in parallel with the processing of step ST31 by the output processing unit 3.

  That is, the control circuit 25 gives the rewritten control signal S41 to the CAM 19 to give the encoded data D1 to the CAM 19 via the signal line 50, and “000” in addition to the code processing selection address in the pre-encoding data storage area RG2. When there is storage data DS (data matching the comparison data DC) storing... 001 ”, a rewrite process for rewriting the encoded data D1 is executed, and the flag bit of the corresponding reference data rewrite processing unit 4 is set. Set to “1” (set state).

  Hereinafter, a specific example will be described using FIG. 8 as an example. When the code processing selection address defined by the read / write address Ad is the address ADp, the other addresses ADq also store “000... 001”. (Recognized by the search result bit CD in the search result storage register R2) Therefore, it is rewritten to the encoded data D1, and the bit of the flag bit storage register R4 corresponding to the address ADp and the address ADq is set to “1”.

  In step ST27, which is executed when YES is determined in step ST24, the encoding process selection address has already been rewritten to the encoded data D1 (the process in step ST30 described above). The storage data DS corresponding to the code processing selection address in the storage area RG2 is read as it is into the register 26, and the register storage encoded data D26 stored in the register 26 is read out as the encoded data D1 via the selector 20.

  At this time, although not shown in FIG. 8, information indicating that the register storage encoded data D26 is output from the register 26 is given to the control circuit 25, whereby the control circuit 25 causes the selector 20 to register the register storage encoded data D26. Is output as encoded data D1.

  Thereafter, in step ST28, it is checked whether the code processing selection address has reached the final address (m-1) (YES) or not (NO). If YES, a reset signal S26 is given from the control circuit 25, After all the flags of the flag bit storage register R4 are reset to “0”, the process returns to step ST21.

  If “NO” in the step ST28, the code processing selection address is incremented by 1 in a step ST29, and then the process returns to the step ST24.

  On the other hand, the occurrence probability calculation circuit 24 of the table creation unit 6 performs pre-encoding data that takes the same value as the comparison data DC of step ST25 in step ST33 in parallel with the matching search process of step ST25 by the encoding processing unit 5. The number of stored data DS (number of coincidence data) in the storage area RG 2 is counted and the count value (occurrence probability calculation result) is output to the maximum value detection / code allocation module 22.

  Then, in step ST34, the maximum value detection / code allocation module 22 is defined as a match signal address (based on the count value from the occurrence probability calculation circuit 24 and the match signal and the match address signal S11b from the address generation circuit 16). The number of counts corresponding to the data before encoding). As described above, the maximum value detection / sign assignment module 22 sequentially recognizes the count number corresponding to the address of the reference data storage region RG1 based on the count result from the occurrence probability calculation circuit 24 and the coincidence address signal S11b. it can.

  Then, in step ST35, whether or not any of the count values corresponding to each address in the reference data storage area RG1 reaches the set value (specified by the set value data D22) (YES) or not (NO). Whether the count value corresponding to the address of the data storage area RG1 reaches the maximum countable value (MAX) (YES) or not (NO), the compression efficiency is a threshold value (specified by the threshold data D21) in step ST37. It is checked whether it is below (YES) or not (NO).

  If YES is determined in step ST35 or ST36, or NO is determined in step ST37, the process proceeds to step ST38.

  In step ST38, the maximum value detection / sign assignment module 22 assigns the Huffman codes in order from the address corresponding to the counter CT having a large count value, based on the occurrence probability calculation result (count value) obtained from the occurrence probability calculation circuit 24. Thus, a new encoding table using the Huffman code for the update encoding table is created.

  Then, the process proceeds to step ST39, and on the basis of the new coding table created in step ST38, the code address signal S22a for defining the address and the code data signal S22b for defining the code data corresponding to the address are selected by the selector 17a. , 17b, the encoding table update process is executed.

  Since the current update coding table is the coding table 13b, the selector 17b uses the enable signal ENb for instructing the active state and the write signal WRb for instructing the writing, and the address defined by the coding address signal S22a. The contents of the encoding table 13b are updated by sequentially outputting to the encoding table 13b the code data DHb indicating the code data defined by the selection address signal SAb and the code data signal S22b.

  Thereafter, the process proceeds to step ST32, and when the cause of execution of step ST38 is NO in step ST37 (when the compression efficiency is lower than the threshold value), the encoding table to be used is changed from the encoding table 13a to the encoding table 13b. Switch to. In addition, when step ST32 is performed after step ST39, it complete | finishes at step ST32 and does not transfer to step ST23. The process moves to step ST23 only when step ST32 is executed after NO is determined in step ST22.

  As described above, in the encoding apparatus according to the second embodiment, the pre-encoding data D0 temporarily stored in the CAM 19 is encoded by the encoding processing unit 5 in real time to maintain the compression efficiency. In addition, it is possible to always prepare an optimal encoding table by the table creation unit 6.

  As a result, coding suitable for Huffman coding that solves the problems of static Huffman coding and adaptive Huffman coding, achieves high-speed Huffman coding processing, and maintains high compression efficiency. A device can be obtained.

  Furthermore, when the reference data rewrite processing unit 4 includes a plurality of data having the same value as the pre-encoding data D0 that has already been encoded into the post-encoding data D1, the pre-encoding data By rewriting the pre-encoding data D0 in the storage area RG2 to the post-encoding data D1, the encoding process by the encoding processing unit 5 can be made unnecessary, so that a higher-speed encoding process can be realized.

(Details of occurrence probability calculation circuit)
(First aspect)
FIG. 10 is a circuit diagram showing a first mode of the occurrence probability calculation circuit 24. As shown in the figure, the occurrence probability calculation circuit 24 is input from m stages of serially connected flip-flops FF1 to FFm that receive the clock CLK in common and receive the reset signal S26 from the control circuit 25 in common at the reset input. Composed.

  The flip-flops FF1 to FFm receive the detection result bits CD1 to CDm in the search result storage register R2 as the encoding processing information S1b, and output the bit data received by the input of the clock CLK received from the outside to the flip-flop of the next stage. Then, the output of the flip-flop FFm is given to the counter 27.

  Therefore, when m clocks CLK are supplied to the flip-flops FF1 to FFm, and the counter 27 counts “1” appearing in the output data of the flip-flop FFm, the detection result bits CD1 to CD1 taken into the flip-flops FF1 to FFm are obtained. The number of “1” (set state) in CDm can be counted.

  As described above, the first aspect of the occurrence probability calculation circuit 24 is the number of coincidence data indicating how many storage data DS matching the reference data DR corresponding to the coincidence signal address exist in the pre-encoding data storage area RG2. Can be obtained as the count value, and the occurrence probability calculation process capable of accurately and rapidly recognizing the appearance information of the latest pre-encoding data D0 can be performed.

  The counter 27 provides the count value to the maximum value detection / sign assignment module 22. The first mode shown in FIG. 10 can be realized only by the flip-flops FF1 to FFm and the counter 27 that constitute one unit of shift register. Therefore, there is an advantage that the implementation is simple. This is effective when aiming for a smaller implementation.

(Second aspect)
FIG. 11 is a circuit diagram showing a second mode of the occurrence probability calculation circuit 24. As shown in the figure, k shift registers SR1 to SRk are provided. Shift registers SR1 to SRk are each configured by a circuit equivalent to flip-flops FF1 to FFm shown in FIG. 10, and shift registers SR1 to SRk receive encoding process information S1b, respectively.

  The outputs of the shift registers SR1 to SRk are received by the subcounters SCT1 to SCTk which are selective counting units, the outputs of the subcounters SCT1 to SCTk are received by the selector 28, and the output of the selector 28 is given to the maximum value detection / sign assignment module 22 Is done.

  The shift registers SR1 to SRk are controlled by the control signal S20a of the control circuit 25 (storage operation, shift operation), and the selector 28 controls the contents of the subcounter SCT to be selected among the subcounters SCT1 to SCTk by the control signal S20b. Is done. The control signals S20a and 20b correspond to the control signal S20 in FIG.

  In such a configuration, in the second mode, the shift registers SR1 to SRk are subjected to pipeline processing, and one shift register SR that receives the encoding processing information S1b and the other shift register SR that performs the shift operation. And are operated independently. For example, when the shift registers SR1, SR3 to SRk are performing the count process (shift operation), the shift register SR2 is caused to capture the encoding process information S1b. When the count processing operation is started with respect to the shift register SR2, the encoding processing information S1b is taken into the shift register SR that has completed other count processing.

  Then, among the sub-counters SCT1 to SCTk, the selector 28 selects the sub-counter SCT for which the counting process from the corresponding shift register SR has been completed, and the count value of the sub-counter SCT for which the counting process has been completed is Is provided to the code allocation module 22.

  In this way, the processing time can be shortened compared to the first mode by executing the pineline counting process between the shift registers SR1 to SRk without overlapping the storing of the encoding process information S1b and the counting process. Can do.

(Third aspect)
FIG. 12 is a circuit diagram showing a third mode of the occurrence probability calculation circuit 24. As shown in the figure, it is composed of partial shift registers SSR1 to SSRj (2 ≦ j <m) and partial counters PCT1 to PCTj which are parallel count units. In the partial shift registers SSR1 to SSRj, encoding processing information S1b is divided into j. Bit detection result groups CDG1 to CDGj are received. Partial counters PCT1 to PCTj are provided on the output side of partial shift registers SSR1 to SSRj.

  The ALU 29 receives the outputs of the partial counters PCT1 to PCTj, and gives the total value to the maximum value detection / sign assignment module 22 as a count value.

  In the third mode, the number of bits to be counted by the partial shift registers SSR1 to SSRj and the partial counters PCT1 to PCTj is (m / j), respectively, and can be operated in parallel. Therefore, in the third mode, by dividing the flip-flops FF1 to FFm of the first mode into j, the latency can be reduced to 1 / j and the high-speed counting can be achieved.

  The third aspect is particularly effective when the compression efficiency changes suddenly depending on the content of the pre-encoding data D0, or when the data tendency does not match the existing encoding table.

(Fourth aspect)
FIG. 13 is a circuit diagram showing a fourth mode of the occurrence probability calculation circuit 24. As shown in the figure, registers CR1 to CRm are provided corresponding to the detection result bits CD1 to CDm, and the registers CR1 to CRm are composed of a plurality of adder groups AD1 that can add outputs between two adjacent registers CR. A second adder comprising a second adder AD2 provided with a first adder group and further connected so that the outputs of two adders AD1 and AD1 adjacent in the first adder group 1 can be added; A group is provided, and thereafter, similarly, p-stage ADp (2 ^p ≧ m) is provided. The adders AD1 to ADp constituting the first to pth adder groups need to increase the number of bits that can be added by one bit as the number of stages increases.

  Then, the output of the adder ADp is given to the maximum value detection / sign assignment module 22 as a count value. The registers CR1 to CRm and the adders (groups) AD1 to ADp are appropriately reset by a reset signal S26 of the control circuit 25.

  As described above, the count value based on the encoding processing information S1b (detection result bits CD1 to CDm) is calculated using a combinational circuit in which the first to pth adder groups including the adders AD1 to ADp are arranged on the tree. Obtainable. Further, by inserting a register between each stage of the first to pth adder groups, it is possible to perform pipeline processing and improve throughput.

(5th aspect)
14 and 15 are an explanatory diagram and a block diagram showing a fifth mode of the occurrence probability calculation circuit 24. FIG. In the fifth aspect, the count value is obtained after the stored data in the pre-encoding data storage area RG2 fetched as shown in FIG. 14 is sorted in descending order as shown in FIG. In the maximum value search by the CAM 19, a comparison is started from the leftmost bit (MSB: Most Significant Bit) of stored data using a mask, and the search data is sequentially set to “1” to the right. Therefore, sorting in descending order can be realized relatively easily.

  When the pre-encoding data storage area RG2 is sorted as shown in FIG. 15, the data in the search result storage register R2 is “1” for the same data as the comparison data DC in the search result storage register R2 at the time of matching search. Are successively arranged in the order of addresses.

  The maximum and minimum coincidence address generation circuit 30 outputs the maximum address corresponding to the bit detection result CD indicating “1” in the search result storage register R2 to the register 39 via the switch 38, and the bit detection result indicating “1”. The minimum address corresponding to the CD is output to the subtracter 40 via the switch 38. The subtractor 40 obtains a count value that is the number of bit detection results CD indicating “1” based on the difference value between the maximum address and the minimum address, and outputs the count value to the maximum value detection / code allocation module 22.

  As described above, the fifth mode is such that the detection result bits CD1 to CD1 in which “1” is set in the data comparison by the coincidence signal and address generation circuit 30, the switch 38, the register 39, and the subtractor 40 constituting the count unit. Based on the maximum / minimum address of CDm, the number of detection result bits CD1 to CDm “1” (set state) can be quickly counted.

  Note that the search result storage register R2, the maximum and minimum matching address generation circuit 30, the switch 38, the register 39, and the subtractor 40 are controlled in operation by a control signal S20 from the control circuit 25.

  The fifth aspect is effective for applications that do not depend on the order of pre-encoding data. In FIG. 15, the selectors 17 a and 17 b and the encoding tables 13 a and 13 b in FIG. 8 are simplified and shown as a selector and an encoding table 34.

(Sixth aspect)
FIG. 16 is a circuit diagram showing a sixth mode of the occurrence probability calculation circuit 24. As shown in the figure, there is provided a sorting circuit 42 capable of fetching all the detection result bits CD1 to CDm of the search result storage register R2, and the sorting circuit 42 internally captures the detection result bits CD1 to CDm and then internally “1”. Sort so that “0” is higher and “0” is lower. That is, the sorting circuit 42 executes a bit sorting process for classifying based on the presence or absence of “1”.

  Then, an EXOR gate group 43 including (m−1) EXOR gates G43 for inputting adjacent bits among the stored bit groups of the sorting circuit 42 is provided, and the output of the EXOR gate group 43 is output by the address generation circuit 44. input.

  The address generation circuit 44 receives the outputs of the (m−1) EXOR gates G43, obtains the count value based on the address corresponding to the output of the EXOR gate G43 indicating “1”, and detects the maximum value / code allocation module 22. Output to. That is, the EXOR gate group 43 and the address generation circuit 44 function as a counting unit.

  In the example of FIG. 16, since only the output of the third EXOR gate G43 from the top in the EXOR gate group 43 is “1”, the address generation circuit 44 counts by recognizing the third EXOR gate G43. The value can be output to the maximum value detection / sign assignment module 22.

  Note that the search result storage register R2, the sorting circuit 42, and the address generation circuit 44 are controlled in operation by the control signal S20 of the control circuit 25.

  In the sixth aspect, the count value is calculated by the EXOR gate group 43 and the address generation circuit 44 based on the bits after sorting in the sorting circuit 42, so that the number of “1” of the detection result bits CD1 to CDm can be quickly obtained. Can be counted.

  In the sixth aspect having such a configuration, the count value can be obtained at high speed. In FIG. 16, the selectors 17 a and 17 b and the encoding tables 13 a and 13 b in FIG. 8 are simplified and shown as a selector and an encoding table 34.

(Seventh aspect)
In general, the CAM includes a priority encoder that selects and outputs one data from a search result bit group in which a plurality of bits indicate a matching state (“1”). The priority encoder system according to the seventh aspect uses a method of counting the bit detection result CD indicating “1” in the search result storage register R2 by using a CAM priority encoder.

  FIG. 17 is a block diagram showing a seventh mode of the occurrence probability calculation circuit 24. As shown in the figure, when the priority encoder 45 receives the detection result bits CD1 to CDm of the search result storage register R2 and the detection result bits CD1 to CDm indicate a plurality of “1” s, only the minimum address “1” is received. The valid bit group is output to the search result storage register R5. In this manner, the priority encoder 45 and the search result storage register R5 constitute a priority encoder unit.

  The contents of the search result storage register R5 are fed back by the reset circuit 47, and the bit in the search result storage register R2 corresponding to the bit position storing “1” in the search result storage register R5 is changed from “1” to “0”. Reset.

  On the other hand, the multi-input OR gate 46 receives all the stored bits of the search result storage register R 5 and outputs the output to the counter 48. The counter 48 counts the number of times “1” is output from the output of the multi-input OR gate 46, and outputs the count result to the maximum value detection / sign assignment module 22 as a count value. As described above, the multi-input OR gate 46 and the counter 48 constitute a count unit. The search result storage register R2 and the counter 48 are reset by a reset signal S26.

  In such a configuration, “1” is output from the multi-input OR gate 46 and counted by the counter 48. At the same time, one “1” in the search result storage register R2 is set by the reset signal S47 from the reset circuit 47. Reset to “0”. When the above-described series of processing is performed as one cycle, “1” is output from the multi-input OR gate 46 for the number of times corresponding to the number of detection result bits CD1 to CDm in the search result storage register R2. Therefore, the counter 48 can accurately count the number of “1” s in the detection result bits CD1 to CDm.

  The seventh aspect can be realized by adding a counter function corresponding to the search result storage register R5, the multi-input OR gate 46, the reset circuit 47, and the counter 48 to the existing CAM macro. Widely, there is an advantage that the number of newly added circuits can be reduced.

  In the seventh aspect, although the number of cycles is required for the number of bits indicating “1” in the search result storage register R2, it is considered that the latency is sufficiently fast to work in parallel with the encoding process. In FIG. 17, the selectors 17 a and 17 b and the encoding tables 13 a and 13 b in FIG. 8 are simplified and shown as a selector and an encoding table 34.

<Others>
The encoding apparatuses according to the first and second embodiments described above have an architecture in which flexible adaptation to various applications, real-time processing, and maintenance of compression efficiency are improved.

  This architecture is a real-time online system such as still image coding for high-definition images such as high-definition images, multimedia data compression such as voice and moving images with the spread of broadband, and videophone and videoconferencing systems using digital communication lines. It is considered that it effectively functions as an encoding device that can perform Huffman encoding of a system used alone, such as a CD, a DVD, and a digital camera device, at high speed and high efficiency.

It is a block diagram which shows the outline of the internal structure of the encoding apparatus which has a CAM based Huffman encoding architecture based on this invention. 1 is an explanatory diagram illustrating an overall configuration of a coding apparatus according to Embodiment 1. FIG. 3 is an explanatory diagram showing a detailed configuration of the encoding apparatus according to Embodiment 1. FIG. 6 is a flowchart illustrating an encoding process and an encoding table creation process in the encoding apparatus according to the first embodiment. FIG. 5 is a conceptual diagram showing a relationship between a CAM 11 and a RAM 13 in the encoded data reading step shown in FIG. It is explanatory drawing which shows the example of a connection of CAM and RAM. FIG. 10 is an explanatory diagram illustrating an overall configuration of a coding apparatus according to a second embodiment. 12 is an explanatory diagram showing a detailed configuration of a coding apparatus according to Embodiment 2. FIG. 10 is a flowchart illustrating an encoding process and an encoding table creation process in the encoding apparatus according to the second embodiment. 6 is a circuit diagram showing a first mode of an occurrence probability calculation circuit according to Embodiment 2. FIG. FIG. 10 is a circuit diagram showing a second mode of the occurrence probability calculation circuit according to the second embodiment. FIG. 10 is a circuit diagram showing a third aspect of the occurrence probability calculation circuit according to the second embodiment. FIG. 10 is a block diagram illustrating a fourth aspect of the occurrence probability calculation circuit according to the second embodiment. FIG. 10 is an explanatory diagram for explaining a fifth aspect of the occurrence probability calculation circuit according to the second embodiment. FIG. 10 is a flock diagram illustrating a fifth aspect of the occurrence probability calculation circuit according to the second embodiment. FIG. 10 is a block diagram illustrating a sixth aspect of the occurrence probability calculation circuit according to the second embodiment. FIG. 10 is a block diagram illustrating a seventh aspect of the occurrence probability calculation circuit according to the second embodiment. It is explanatory drawing which shows the concept of CAM.

Explanation of symbols

1, 5 encoding processing unit, 2, 6 table creation unit, 3 output processing unit, 4 reference data rewrite processing unit, 11, 19 CAM, 13a, 13b encoding table, 17 switch, 21, 24 occurrence probability calculation circuit, 22 Maximum value detection / sign assignment module, 23, 25 control circuit, 41 feedback circuit.

Claims (12)

Receiving pre-encoding data, encoding the pre-encoding data using a target encoding table to generate post-encoding data, and encoding processing information including the appearance status of the pre-encoding data An encoding processing unit to output;
A table for performing occurrence probability calculation processing of the pre-encoding data based on the encoding processing information and creating an update encoding table based on the calculation result in parallel with the encoding processing by the encoding processing unit With a creation department,
The table creation unit, when the compression efficiency in the encoding process does not satisfy a predetermined standard, the use target encoding table is replaced with the update encoding table,
Encoding device. The encoding device according to claim 1, comprising:
The use target encoding table and the update encoding table each include a table of a format for storing read data in association with addresses,
The encoding processing unit includes a CAM having a reference data storage area in which all patterns of pre-encoding data are stored as a plurality of reference data in association with addresses,
At the time of matching search, the CAM uses predetermined data before encoding as data to be encoded, and generates a match signal address that is an address of the reference data that matches the data to be encoded among the plurality of reference data. ,
The encoding processing unit refers to the use target encoding table and outputs read data corresponding to the coincidence signal address as the encoded data.
Encoding device. The encoding device according to claim 2, wherein
The CAM further includes a first search result storage register for storing a plurality of first search result bits corresponding to the plurality of reference data, and the plurality of first search result bits are stored in the match search. Set in a set state when the corresponding reference data and the encoding target data match,
The table creation unit has an occurrence probability calculation circuit that performs the occurrence probability calculation process by counting the number of appearances of the plurality of reference data units based on the contents of the plurality of first search result bits.
Encoding device. The encoding device according to claim 2, wherein
The CAM stores a pre-encoding data storage area for storing a predetermined number of pre-encoding data as a predetermined number of stored data and a predetermined number of second search result bits corresponding to the predetermined number of stored data. 2 search result storage registers,
The CAM reads, as the encoding target data, one data among the predetermined number of stored data stored in the pre-encoding data storage area during the match search, and the encoding target data and the predetermined number of data Each stored data is compared, and the predetermined number of second search result bits in the second search result storage register is set to a set state when the corresponding stored data matches the encoding target data,
The table creation unit includes an occurrence probability calculation circuit that performs the occurrence probability calculation process by counting the number of bits in a set state among the predetermined number of second search result bits.
Encoding device. The encoding device according to claim 4, comprising:
When there is a plurality of data having the same value as the encoding target data among the predetermined number of stored data during the matching search, generation of encoded data corresponding to the encoding target data by the encoding processing unit A rewrite processing unit for performing a rewrite process of rewriting data having the same value as the data to be encoded among the predetermined number of stored data in the pre-encoding data storage area later with the encoded data,
The CAM further includes a flag bit storage register provided corresponding to the predetermined number of stored data, each storing a predetermined number of rewrite flags indicating whether or not the rewrite processing is executed, , Setting the rewrite flag corresponding to the stored data that is the target of the rewrite processing to a set state,
When the corresponding rewrite flag is in the set state when the storage processing unit reads the storage data as the encoding target data, the storage processing data is directly output as encoded data without being encoded.
Encoding device. An encoding device according to claim 4 or claim 5, wherein
The occurrence probability calculation circuit includes:
At least one shift register that collectively receives the predetermined number of second search result bits;
A counting unit that counts the number of set states of the predetermined number of second search result bits fetched into the at least one shift register.
Encoding device. The encoding device according to claim 6, comprising:
The at least one shift register includes a plurality of shift registers each capable of fetching the predetermined number of second search result bits at once;
The plurality of shift registers, with respect to the predetermined number of second search result bits obtained sequentially, one shift register among the plurality of shift registers captures the predetermined number of second search result bits, Pipeline processing in which the shift register performs a shift operation is possible,
The counting unit includes a selective counting unit that selectively counts the outputs of the plurality of shift registers.
Encoding device. The encoding device according to claim 6, comprising:
The at least one shift register includes a plurality of partial shift registers each capturing a part of the predetermined number of second search result bits;
The counting unit includes a parallel counting unit that counts in parallel the number of set states of a part of the predetermined number of second search result bits fetched into each of the plurality of partial shift registers, and obtains a total thereof.
Encoding device. An encoding device according to claim 4 or claim 5, wherein
The occurrence probability calculation circuit includes:
An adder group that performs the occurrence probability calculation process by sequentially adding the predetermined number of second search result bits in a tree-like manner in units of bits;
Encoding device. An encoding device according to claim 4 or claim 5, wherein
The pre-encoding data storage area in the CAM has a sorting function for sorting the predetermined number of stored data based on the magnitude relationship of data,
The occurrence probability calculation circuit includes:
A counting unit that counts the number of set states of the predetermined number of second search result bits based on the corresponding addresses of the predetermined number of second search result bits at the time of matching search for the pre-encoding data storage area after sorting including,
Encoding device. An encoding device according to claim 4 or claim 5, wherein
The occurrence probability calculation circuit includes:
A sorting circuit that takes in the predetermined number of second search result bits as the predetermined number of stored bits and performs a bit sorting process for classifying based on the presence / absence of a set state of the predetermined number of stored bits;
A counting unit that counts the number of set states of the predetermined number of stored bits based on the predetermined number of stored bits in the sorting circuit after the bit sorting process.
Encoding device. An encoding device according to claim 4 or claim 5, wherein
The occurrence probability calculation circuit includes:
Bit data after priority processing is performed by receiving the predetermined number of second search result bits and performing an encoding process for validating only one bit when a plurality of bits among the predetermined number of second search result bits are set. A priority encoding unit that outputs
A counting unit capable of recognizing the presence or absence of a set bit in the bit data after the priority processing;
A reset circuit that resets a set state of a bit corresponding to a bit indicating a match in the bit data after priority processing among the predetermined number of second search result bits,
The priority encoding unit repeatedly performs the encoding process until there is no set bit in the predetermined number of second search result bits,
The counting unit counts the number of set states in the predetermined number of second search result bits immediately after the match search based on the number of times the priority-processed bit data including the set state bits is received.
Encoding device.

Images