JP5472610B2 - Method and apparatus for encoding / decoding numeric data string - Google Patents

Description

  The present invention relates to a technique for encoding a numeric data string composed of fixed-length bits using a variable-length bit string and, on the contrary, decoding the data.

  Data compression / decompression techniques for digital data files are used in various fields as a method for reducing the file size while maintaining the amount of information. In particular, since data files such as audio, image, and video have high information redundancy, it is common to handle data files in a compressed state.

  One of the important basic principles of the data compression technique is to encode a numerical data string composed of fixed-length bits using a variable-length bit string. Data of fixed length bits such as 8 bits and 16 bits are suitable for arithmetic processing by the CPU, but there is a problem that the data capacity is increased because many redundant bits are included. Therefore, by encoding a numerical data string composed of fixed-length bits using a variable-length bit string and deleting redundant bits, the data capacity can be compressed while maintaining the amount of information.

  Another important basic principle of data compression technology is the use of an expression format using run length. For example, when the run-length expression format is adopted for numerical data indicating 0, the data capacity can be reduced by counting the number of consecutive 0s and recording the count value as information. In particular, an expression format using this run length is effective for compressing image data and video data.

  Currently, data compression methods such as the JPEG method, MPEG method, and LHA method, which are the mainstream, employ an encoding technique using a Huffman code that is a variable length code. In the commonly used baseline JPEG method, an image is divided into 8 × 8 pixel blocks, and discrete cosine transform (DCT), quantization, and Huffman coding are sequentially performed for each block. In this case, in Huffman coding, processing divided into a DC component and an AC component is performed. In any case, by encoding a numeric data string composed of fixed-length bits using a variable-length bit string, Redundant bits are reduced. For the AC component, the run length expression format is further adopted for the numerical data indicating 0, and the data capacity can be greatly reduced.

  For example, the following Patent Documents 1 and 2 disclose an encoding device that compresses image data using a JPEG method using a Huffman code. Patent Document 3 below discloses a decoding apparatus that efficiently decodes image data compressed by the JPEG method.

Japanese Patent Laid-Open No. 5-110863 Japanese Patent Laid-Open No. 5-114240 JP-A-8-316844

  As described above, since a data string encoded using a variable-length bit string is inappropriate for handling by the CPU, when actually used, it is decoded and is a numerical value consisting of the original fixed-length bits. It is necessary to return to the data column. However, the encoded data consisting of variable-length bit strings does not have a fixed bit position as a delimiter, so the boundaries of the processing units are unclear. In the conventional general method, decoding is performed by parallel processing. I can't. That is, the decoding process must be performed in order from the top using one decoding processing unit. For this reason, the decoding process takes time, and in particular, in the case of video data that requires display processing in real time, there arises a problem that smooth reproduction is hindered.

  In the above-mentioned Patent Document 3, as a solution to such a problem, an operation of creating boundary information for specifying the boundary of the processing unit of the encoded data sequence is performed at the time of the first decoding process, and the second and subsequent times. In this decoding process, a technique is disclosed in which an encoded data string is divided into a plurality of partial data based on the boundary information, and decoding is performed by parallel processing using a plurality of decoding processing units. If this technique is used, efficient decoding by parallel processing becomes possible during the second and subsequent decoding processes. However, parallel processing cannot be performed at the time of the first decoding process, and the technology does not provide a fundamental solution.

  Therefore, the present invention aims to provide a special encoding technique that enables a parallel processing at a decoding stage while encoding a numerical data string composed of fixed-length bits using a variable-length bit string. And Another object of the present invention is to provide a technique for decoding data encoded by the encoding technique by parallel processing using a plurality of decoding processing units.

(1) According to a first aspect of the present invention, there is provided a numerical data string encoding method for encoding a numerical data string composed of fixed-length bits using a variable-length bit string.
The arithmetic processing unit generates actual data representing specific numerical data using a variable-length bit string, and adds an identification code having at least information indicating the bit length of the actual data to the head of the actual data. This generates unit code data having information indicating at least the specific numerical data itself, and executes a process of arranging the generated plurality of unit code data in order and outputting them as an encoded data string,
When selecting an identification code to be added, an encoding table indicating at least “a correspondence relationship between a plurality of bit lengths within a predetermined range and an identification code corresponding to the bit length” is used, and the table However, when focusing on any identification code in the table, when the bit length of the target identification code itself is a, the a-bit portion from the beginning is the same as the target identification code. No identification code exists in this table, and when a bit length corresponding to the identification code of interest is b, “N” is an integer greater than or equal to 2 The table satisfies the condition of “a + b = k × N” (where k is an arbitrary integer).

(2) According to a second aspect of the present invention, in the above-described numerical data string encoding method according to the first aspect,
Arithmetic processing unit
A data input stage for inputting a numeric data string to be encoded;
A table input stage for inputting a coding table indicating a unique identification code corresponding to each bit length;
A data extraction stage for sequentially extracting individual numerical data from the input numerical data string;
An actual data generation stage for generating actual data by deleting redundant bits from the extracted numerical data;
An identification code selection step of selecting an identification code corresponding to the bit length of the generated actual data with reference to the encoding table;
A unit code data generation stage for generating unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
A step of repeatedly performing a data extraction step, an actual data generation step, an identification code selection step, and a unit code data generation step for each of the numerical data constituting the input numerical data string;
A data output stage for arranging the generated unit code data in order and outputting them as an encoded data string;
And run
The encoding table is
It is a table showing the correspondence between individual bit lengths and unique identification codes corresponding to the bit lengths for a plurality of bit lengths within a predetermined range sufficient to represent actual data,
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. The code does not exist in this table, and when the bit length corresponding to the target identification code is b, “a + b = N” is a predetermined reference bit length N (where N is an integer of 2 or more). The table satisfies the condition “k × N” (where k is an arbitrary integer).

(3) According to a third aspect of the present invention, in the above-described numerical data string encoding method according to the second aspect,
In the actual data generation stage, as actual data indicating the extracted numerical data, when the numerical data is data indicating 0, a virtual bit string having a bit length of 0 is represented as data indicating a positive value. Is a variable-length bit string that does not include 0 at the beginning, and a variable-length bit string that does not include 1 at the beginning if the data indicates a negative value.

(4) According to a fourth aspect of the present invention, in the above-described numerical data string encoding method according to the first aspect,
Arithmetic processing unit
A data input stage for inputting a numeric data string to be encoded;
A table input stage for inputting a two-dimensional encoding table indicating a unique identification code corresponding to a combination of individual bit lengths and individual run length values;
A data extraction stage for sequentially extracting individual numerical data from the input numerical data string;
When the extracted numerical data is data indicating 0 and the count value so far has not reached the maximum value Rmax, the number of times the numerical data indicating 0 is continuously extracted is counted as a run length value. A run length value counting stage;
When the extracted numerical data is data indicating a positive value, a variable-length bit string that does not include a leading zero is generated as actual data indicating the numerical data, and the extracted numerical data is data indicating a negative value In some cases, a variable-length bit string not including 1 at the beginning is generated as actual data indicating the numerical data, the extracted numerical data is data indicating 0, and the count value has reached the maximum value Rmax. A real data generation stage for generating a virtual bit string having a bit length of 0 as real data,
With reference to the two-dimensional encoding table, an identification code corresponding to a combination of the bit length of the generated actual data and the run length value when the actual data is generated is selected, and the count value is set to 0 An identification code selection stage to be reset;
A unit code data generation stage for generating unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
The data extraction stage is repeatedly executed for each of the numerical data constituting the input numerical data string, and the run length value counting stage, the actual data generation stage, the identification code selection stage, and the unit code data generation stage are performed as necessary. Repeated steps,
A data output stage for arranging the generated unit code data in order and outputting them as an encoded data string;
And run
When the encoding table has a predetermined maximum run length value determined in advance as Rmax, a plurality of bit lengths within a predetermined range sufficient for expressing actual data and a plurality of types within a range up to Rmax Is a table showing a correspondence relationship between each combination and a unique identification code corresponding to the combination for each combination of run length values of
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. The code does not exist in this table, and when the bit length corresponding to the target identification code is b, “a + b = N” is a predetermined reference bit length N (where N is an integer of 2 or more). The table satisfies the condition “k × N” (where k is an arbitrary integer).

(5) According to a fifth aspect of the present invention, in the above-described numerical data string encoding method according to the fourth aspect,
In the data extraction stage, when extracting numeric data, it is checked whether or not “zero persistent state that all numeric data subsequent to the end of the numeric data string including the numeric data to be extracted is 0”. When an investigation process is executed and it is confirmed that the investigation process is in a zero-permanent state,
In the actual data generation stage, a virtual bit string having a bit length of 0 is generated as actual data, and in the identification code selection stage, a termination code indicating a zero permanent state is selected as an identification code.

(6) According to a sixth aspect of the present invention, in the above-described numerical data string encoding method according to the first to fifth aspects,
As the appearance frequency of the bit length b of actual data or the appearance frequency of the combination of the bit length b and the run length value R is higher, an encoding table in which an identification code having a shorter bit length a is associated is used. It is what I did.

(7) According to a seventh aspect of the present invention, in the above-described numerical data string encoding method according to the sixth aspect,
A frequency counting stage for counting the appearance frequency of the bit length b of the actual data or the appearance frequency of the combination of the bit length b and the run length value R for the numerical data string to be encoded;
The frequency of occurrence of the bit length b of the actual data or the bit by performing the process of exchanging the contents of the table for the bit lengths b having an integer multiple difference of the reference bit length N in the existing standard encoding table A table modification stage for generating a modified encoding table in which an identification code having a shorter bit length a is associated with an increase in the appearance frequency of the combination of the length b and the run length value R;
And execute
In the identification code selection stage, the identification code is selected with reference to the corrected encoding table.

(8) According to an eighth aspect of the present invention, in the above-described numerical data string encoding method according to the first to seventh aspects,
In the data output stage, a data file including the encoded data string and the encoding table used for the encoding process is output.

(9) According to a ninth aspect of the present invention, in the above-described numerical data string encoding method according to the first to seventh aspects,
In the data output stage, a data file including an encoded data string and table specifying information for specifying an encoding table used for encoding processing is output.

(10) According to a tenth aspect of the present invention, a numerical data sequence that is a target of encoding is restored for the encoded data sequence encoded by the numerical data sequence encoding method according to the second aspect described above. In the decoding method of the numerical data sequence to be performed,
An arithmetic processing device including a plurality of M decoding processing units is provided.
A data input stage for inputting an encoded data sequence to be decoded;
A table input stage for inputting an encoding table used for encoding;
Decoding of a plurality of M units each having a function of performing decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax when the maximum bit length of unit code data is Umax) A data distribution stage for distributing a part of the encoded data string as partial data to the processing unit;
A decoding process stage for performing a decoding process of extracting numerical data corresponding to actual data from each distributed partial data while referring to an encoding table by parallel processing by M decoding processing units;
A data organization stage for selecting a result of the decryption processing by the M decryption processing units and generating a decrypted data sequence in which numerical data corresponding to individual actual data are arranged;
A data output stage for outputting the generated decrypted data sequence;
And run
In the data distribution stage, bit strings from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the head of the undecoded portion of the encoded data sequence , Repeating the process of distributing to the i-th unit (i = 1 to M) until decoding of all parts of the encoded data sequence is completed,
In the decryption processing stage, each of the M decryption processing units performs processing for extracting numerical data corresponding to actual data from the head of the distributed partial data each time new partial data is distributed. ,
In the data organization stage, when the processing results are obtained from the M decoding processing units by one parallel processing, the first unit is first determined as the first selection unit, and a normal decoding process is performed by this selection unit. The process of recognizing the last bit performed and determining as another newly adopted unit another unit to which the partial data having the bit immediately after the last bit as the first bit is distributed is performed as much as possible. Numeric data that has been successfully decoded by the selected unit is collected, and the decoded data string is generated by arranging the numeric data collected by one or more parallel processes.

(11) According to an eleventh aspect of the present invention, a numerical data sequence that is a target of encoding is restored for the encoded data sequence encoded by the numerical data sequence encoding method according to the fourth aspect described above. In the decoding method of the numerical data sequence to be performed,
An arithmetic processing device including a plurality of M decoding processing units is provided.
A data input stage for inputting an encoded data sequence to be decoded;
A table input stage for inputting a two-dimensional encoding table used for encoding;
Decoding of a plurality of M units each having a function of performing decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax when the maximum bit length of unit code data is Umax) A data distribution stage for distributing a part of the encoded data string as partial data to the processing unit;
A run-length value indicating the number of times numeric data indicating 0 is enumerated from the partial data distributed by referring to the two-dimensional encoding table by parallel processing by M decoding processing units, and a numerical value indicating 0 A decoding process stage for performing a decoding process to extract numerical data corresponding to actual data following the data;
A data organization stage for selecting a result of the decoding processing by the M decoding processing units and generating a decoded data string in which numerical data indicating 0 and numerical data corresponding to individual real data are arranged;
A data output stage for outputting the generated decrypted data sequence;
And run
In the data distribution stage, bit strings from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the head of the undecoded portion of the encoded data sequence , Repeating the process of distributing to the i-th unit (i = 1 to M) until decoding of all parts of the encoded data sequence is completed,
In the decoding process stage, each of the M decoding processing units takes out the numerical data corresponding to the run length value and the actual data from the head of the distributed partial data each time new partial data is distributed. Process
In the data organization stage, when the processing results are obtained from the M decoding processing units by one parallel processing, the first unit is first determined as the first selection unit, and a normal decoding process is performed by this selection unit. The process of recognizing the last bit performed and determining as another newly adopted unit another unit to which the partial data having the bit immediately after the last bit as the first bit is distributed is performed as much as possible. Numeric data that has been successfully decrypted by the selected unit is collected, and the decrypted data string is generated by arranging the numeric data based on the information collected by one or more parallel processes. Is.

(12) According to a twelfth aspect of the present invention, “at least an identification code indicating a predetermined bit length followed by actual data including a bit string having the bit length, the total length being a predetermined reference Corresponds to at least individual actual data for an encoded data string configured by arranging a plurality of unit code data set to be an integer multiple of bit length N (where N is an integer of 2 or more) In the decoding method of the numerical data string for restoring the numerical data to be performed,
Dividing the encoded data string in units of an integer multiple of N bits to generate a plurality of partial data, and distributing each partial data to a plurality of M decoding processing units;
By performing parallel processing of a plurality of M decoding processing units, a decoding process is performed on the distributed partial data,
A decoded data string is generated by arranging numerical data that have been normally decoded.

(13) According to a thirteenth aspect of the present invention, in the above-described numerical data sequence decoding method according to the twelfth aspect,
“A data in which actual data consisting of a bit string having the bit length is arranged following an identification code indicating a predetermined bit length, and the total length is a predetermined reference bit length N (where N is an integer of 2 or more) In order to restore numerical data corresponding to individual actual data for an encoded data string configured by arranging a plurality of unit code data (maximum bit length Umax) set to be an integral multiple of ,
An arithmetic processing device including a plurality of M decoding processing units is provided.
A data input stage for inputting an encoded data sequence to be decoded;
A table input stage for inputting an encoding table indicating a specific bit length corresponding to each identification code;
A part of the encoded data string is assigned to a plurality of M decoding processing units each having a function of performing decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax). A data distribution stage to distribute as partial data;
A decoding process stage for performing a decoding process of extracting numerical data corresponding to actual data from each distributed partial data while referring to an encoding table by parallel processing by M decoding processing units;
A data organization stage for selecting a result of the decryption processing by the M decryption processing units and generating a decrypted data sequence in which numerical data corresponding to individual actual data are arranged;
A data output stage for outputting the generated decrypted data sequence;
And run
In the data distribution stage, bit strings from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the head of the undecoded portion of the encoded data sequence , Repeating the process of distributing to the i-th unit (i = 1 to M) until decoding of all parts of the encoded data sequence is completed,
In the decryption processing stage, each of the M decryption processing units performs processing for extracting numerical data corresponding to actual data from the head of the distributed partial data each time new partial data is distributed. ,
In the data organization stage, when the processing results are obtained from the M decoding processing units by one parallel processing, the first unit is first determined as the first selection unit, and a normal decoding process is performed by this selection unit. The process of recognizing the last bit performed and determining as another newly adopted unit another unit to which the partial data having the bit immediately after the last bit as the first bit is distributed is performed as much as possible. Numeric data that has been successfully decoded by the selected unit is collected, and the decoded data string is generated by arranging the numeric data collected by one or more parallel processes.

(14) According to a fourteenth aspect of the present invention, in the encoding method of the numerical data string according to the thirteenth aspect described above,
In the decoding process stage, each of the M decoding processing units performs processing for extracting numerical data corresponding to actual data from the head of the distributed partial data each time new partial data is distributed. The normal decoding process is continued as much as possible.

(15) According to a fifteenth aspect of the present invention, in the above-described numerical data string encoding method according to the thirteenth aspect,
Numerical data corresponding to actual data for one unit code data from the beginning of the distributed partial data each time the M partial decoding processing units distribute new partial data at the decoding processing stage. The process for taking out only is performed.

(16) According to a sixteenth aspect of the present invention, in the encoding method of the numerical data string according to the thirteenth aspect described above,
In the decoding process stage, each of the first to (M−1) -th units among the M decoding processing units is distributed each time new partial data is distributed. The process for extracting only the numerical data corresponding to the actual data for one unit code data is performed from the beginning of the unit, and the M-th unit is distributed each time new partial data is distributed. The process for extracting the numerical data corresponding to the actual data from the head of the partial data is continued as long as normal decoding processing is possible.

(17) According to a seventeenth aspect of the present invention, in the method for decoding a numeric data string according to the twelfth aspect described above,
“Subsequent to an identification code indicating a combination of a predetermined bit length and a predetermined run length value, it has a structure in which real data including a bit string having the bit length is arranged, and numerical data indicating 0 is expressed as the run length. Indicates a data string in which numerical data corresponding to actual data is arranged after being enumerated a number of times corresponding to the value, and the total length is set to be an integral multiple of a predetermined reference bit length N (where N is an integer of 2 or more) In order to restore the original data sequence in which numerical data indicating 0 and individual actual data are arranged for an encoded data sequence configured by arranging a plurality of sets of unit code data (maximum bit length Umax) ” ,
An arithmetic processing device including a plurality of M decoding processing units is provided.
A data input stage for inputting an encoded data sequence to be decoded;
A table input stage for inputting a two-dimensional encoding table indicating a combination of a specific bit length corresponding to each identification code and a specific run length value;
A part of the encoded data string is assigned to a plurality of M decoding processing units each having a function of performing decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax). A data distribution stage to distribute as partial data;
A run-length value indicating the number of times numeric data indicating 0 is enumerated from the partial data distributed by referring to the two-dimensional encoding table by parallel processing by M decoding processing units, and a numerical value indicating 0 A decoding process stage for performing a decoding process to extract numerical data corresponding to actual data following the data;
A data organization stage for selecting a result of the decoding processing by the M decoding processing units and generating a decoded data string in which numerical data indicating 0 and numerical data corresponding to individual real data are arranged;
A data output stage for outputting the generated decrypted data sequence;
And run
In the data distribution stage, bit strings from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the head of the undecoded portion of the encoded data sequence , Repeating the process of distributing to the i-th unit (i = 1 to M) until decoding of all parts of the encoded data sequence is completed,
In the decoding process stage, each of the M decoding processing units takes out the numerical data corresponding to the run length value and the actual data from the head of the distributed partial data each time new partial data is distributed. Process
In the data organization stage, when the processing results are obtained from the M decoding processing units by one parallel processing, the first unit is first determined as the first selection unit, and a normal decoding process is performed by this selection unit. The process of recognizing the last bit performed and determining as another newly adopted unit another unit to which the partial data having the bit immediately after the last bit as the first bit is distributed is performed as much as possible. Numeric data that has been successfully decrypted by the selected unit is collected, and the decrypted data string is generated by arranging the numeric data based on the information collected by one or more parallel processes. Is.

(18) According to an eighteenth aspect of the present invention, in the numerical data sequence decoding method according to the seventeenth aspect described above,
In the decoding process stage, each of the M decoding processing units extracts numerical data corresponding to the run-length value and the actual data from the head of the distributed partial data each time new partial data is distributed. This process is to continue normal decryption processing as much as possible.

(19) According to a nineteenth aspect of the present invention, in the numerical data sequence decoding method according to the seventeenth aspect described above,
In the decoding process stage, each time the M decoding processing units distribute new partial data, the run length value and the actual data for one unit code data from the head of the distributed partial data. A process for extracting only the corresponding numerical data is performed.

(20) According to a twentieth aspect of the present invention, in the numerical data string decoding method according to the seventeenth aspect described above,
In the decoding process stage, each of the first to (M−1) -th units among the M decoding processing units is distributed each time new partial data is distributed. Each time the M-th unit distributes new partial data, it performs a process for extracting only the run-length value for one unit code data and the numerical data corresponding to the actual data. The process for extracting the numerical data corresponding to the run length value and the actual data from the head of the distributed partial data is continued as much as possible for normal decoding processing.

(21) According to a twenty-first aspect of the present invention, in the numerical data sequence decoding method according to the seventeenth to twentieth aspects described above,
In the decoding process stage, each of the M decoding processing units restores the original data by arranging the numerical data corresponding to the actual data after arranging the numerical data indicating 0 as many times as the run-length value. Execute the process,
A decoding method of a numerical data string, wherein a decoded data string is generated by arranging restored data in a data organization stage.

(22) According to a twenty-second aspect of the present invention, in the above-described numerical data string decoding method according to the seventeenth to twentieth aspects,
In the decoding process stage, each of the M decoding processing units executes a process of outputting the run length value and the numerical data corresponding to the actual data as they are,
In the data organization stage, based on the information collected from each adopted unit, the original data is restored by arranging the numerical data indicating 0 for the number of times corresponding to the run-length value and arranging the numerical data corresponding to the actual data. A decoding method for a numerical data string, wherein the decoding data string is generated by arranging the restored data by performing a process to perform

(23) According to a twenty-third aspect of the present invention, in the above-described numerical data string decoding method according to the thirteenth to twenty-second aspects,
When a data file including an encoded data string and an encoding table used for encoding processing is given,
In the data input stage, perform the process of extracting the encoded data string from the data file,
In the table input stage, processing for extracting the encoding table from the data file is performed.

(24) According to a twenty-fourth aspect of the present invention, in the above-described numerical data string decoding method according to the thirteenth to twenty-second aspects,
When a data file including an encoded data string and table specifying information for specifying an encoding table used for encoding processing is given,
In the data input stage, perform the process of extracting the encoded data string from the data file,
In the table input stage, after performing the process of extracting the table specifying information from the data file, the table specified by the table specifying information is selected and used.

(25) According to a twenty-fifth aspect of the present invention, in the method for decoding numerical data strings according to the thirteenth to twenty-fourth aspects described above,
In the data distribution stage, partial data is distributed to a plurality of M decoding processing units such that M ≧ 1 + L / N,
In the decoding process stage, parallel processing by these M decoding processing units is performed.

(26) According to a twenty-sixth aspect of the present invention, in a numerical data sequence encoding device that encodes a numerical data sequence composed of fixed-length bits using a variable-length bit sequence,
A data storage unit for inputting and storing a numeric data sequence to be encoded;
A table storage unit for storing a coding table indicating a unique identification code corresponding to each bit length;
A data extraction unit that sequentially extracts individual numerical data from a numerical data string stored in the data storage unit;
An actual data generation unit that generates actual data by deleting redundant bits from the extracted numerical data;
An identification code selection unit that selects an identification code corresponding to the bit length of the generated actual data with reference to the encoding table;
A unit code data generation unit that generates unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
A data output unit that arranges the generated unit code data in order and outputs the encoded data as an encoded data sequence;
Provided,
The encoding table is
It is a table showing the correspondence between individual bit lengths and unique identification codes corresponding to the bit lengths for a plurality of bit lengths within a predetermined range sufficient to represent actual data,
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. The code does not exist in this table, and when the bit length corresponding to the target identification code is b, “a + b = N” is a predetermined reference bit length N (where N is an integer of 2 or more). The table satisfies the condition “k × N” (where k is an arbitrary integer).

(27) According to a twenty-seventh aspect of the present invention, in the numerical data string encoding device according to the twenty-sixth aspect described above,
When the actual data generation unit is a real data indicating the extracted numerical data, when the numerical data is data indicating 0, a virtual bit string having a bit length of 0 is represented by a positive value. Is a variable-length bit string that does not include 0 at the beginning, and a variable-length bit string that does not include 1 at the beginning if the data indicates a negative value.

(28) According to a twenty-eighth aspect of the present invention, in a numerical data sequence encoding device that encodes a numerical data sequence composed of fixed-length bits using a variable-length bit sequence,
A data storage unit for inputting and storing a numeric data sequence to be encoded;
A table storage unit for storing a two-dimensional encoding table indicating a unique identification code corresponding to a combination of individual bit lengths and individual run length values;
A data extraction unit that sequentially extracts individual numerical data from a numerical data string stored in the data storage unit;
When the extracted numerical data is data indicating 0 and the count value so far has not reached the maximum value Rmax, the number of times the numerical data indicating 0 is continuously extracted is counted as a run length value. If the extracted numerical data is data indicating a positive value, a process of generating a variable-length bit string that does not include a leading zero as actual data indicating the numerical data is performed. When the data is a data indicating a negative value, a process of generating a variable-length bit string not including 1 at the head is performed as actual data indicating the numerical data, and the extracted numerical data is data indicating 0 When the count value has reached the maximum value Rmax, an actual data generation unit that generates a virtual bit string having a bit length of 0 as actual data;
With reference to the two-dimensional encoding table, an identification code corresponding to a combination of the bit length of the generated actual data and the run length value when the actual data is generated is selected, and the count value is set to 0 An identification code selection unit to be reset;
A unit code data generation unit that generates unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
A data output unit that arranges the generated unit code data in order and outputs the encoded data as an encoded data sequence;
Provided,
When the encoding table has a predetermined maximum run length value determined in advance as Rmax, a plurality of bit lengths within a predetermined range sufficient for expressing actual data and a plurality of types within a range up to Rmax Is a table showing a correspondence relationship between each combination and a unique identification code corresponding to the combination for each combination of run length values of
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. The code does not exist in this table, and when the bit length corresponding to the target identification code is b, “a + b = N” is a predetermined reference bit length N (where N is an integer of 2 or more). The table satisfies the condition “k × N” (where k is an arbitrary integer).

(29) According to a twenty-ninth aspect of the present invention, in the numerical data string encoding device according to the twenty-eighth aspect described above,
When the data extraction unit extracts the numerical data, it checks whether or not “a zero-permanent state in which all the numerical data subsequent to the end of the numerical data string including the numerical data to be extracted is 0” is in effect. Run the investigation process,
When the real data generation unit is confirmed to be in a zero-permanent state by the investigation process, a virtual bit string having a bit length of 0 is generated as real data,
The identification code selection unit is configured to select a termination code indicating the zero permanent state as an identification code when it is confirmed by the investigation process that the zero permanent state is established.

(30) According to a thirtieth aspect of the present invention, in the numerical data sequence encoding device according to the twenty-sixth to twenty-ninth aspects described above,
The encoding table stored in the table storage unit has a shorter bit length a as the appearance frequency of the bit length b of the actual data or the appearance frequency of the combination of the bit length b and the run length value R increases. The encoding table is associated with an identification code.

(31) According to a thirty-first aspect of the present invention, in the numerical data string encoding device according to the thirtieth aspect described above,
A frequency counting unit that counts the appearance frequency of the bit length b of the actual data or the appearance frequency of the combination of the bit length b and the run length value R for the numerical data string stored in the data storage unit;
The frequency of occurrence of the bit length b of the actual data or the bit by performing the process of exchanging the contents of the table for the bit lengths b having an integer multiple difference of the reference bit length N in the existing standard encoding table A table for generating a modified encoding table in which an identification code having a shorter bit length a is associated with each other as the appearance frequency of the combination of the length b and the run length value R is higher, and storing the table in the table storage unit Correction part,
Is further provided.

(32) According to a thirty-second aspect of the present invention, in the numerical data sequence encoding device according to the twenty-sixth to thirty-first aspects described above,
The data output unit outputs the encoding table stored in the table storage unit or table specifying information for specifying the encoding table together with the encoded data string.

(33) According to a thirty-third aspect of the present invention, “the identification code indicating a predetermined bit length is followed by actual data including a bit string having the bit length, and the total length is a predetermined reference bit. For each encoded data string formed by arranging a plurality of unit code data (maximum bit length Umax) set to be an integral multiple of the length N (where N is an integer of 2 or more) A numerical data string decoding device for restoring numerical data corresponding to actual data,
A data storage unit for inputting and storing an encoded data sequence to be decoded;
A table storage unit for storing a coding table indicating a specific bit length corresponding to each identification code;
A plurality of M decoding processing units that perform decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax) in parallel,
A data distribution unit that distributes a part of the encoded data sequence stored in the data storage unit as partial data to the M decoding processing units;
A data organization unit that selects a result of the decryption processing by the M decryption processing units and generates a decrypted data sequence in which numerical data corresponding to individual actual data are arranged;
A data output unit for outputting the generated decrypted data sequence;
Provided,
The data distributing unit counts the bit sequence from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the head of the undecoded unit of the encoded data sequence. , Repeating the process of distributing to the i-th unit (i = 1 to M) until decoding of all parts of the encoded data sequence is completed,
The M decoding processing units have a function of performing a decoding process of extracting numerical data corresponding to actual data from each distributed partial data while referring to the encoding table, and new partial data is distributed. Each time, the processing to extract the numerical data corresponding to the actual data from the beginning of the distributed partial data,
When the processing result is obtained from the M decoding processing units by one parallel processing, the data organization unit first determines the first unit as the first selected unit, and the selected decoding unit performs normal decoding processing. The process of recognizing the last bit performed and determining as another newly adopted unit another unit to which the partial data having the bit immediately after the last bit as the first bit is distributed is performed as much as possible. Numeric data that has been successfully decoded by the selected unit is collected, and the decoded data string is generated by arranging the numeric data collected by one or more parallel processes.

(34) According to a thirty-fourth aspect of the present invention, in the numerical data sequence decoding apparatus according to the thirty-third aspect described above,
Each of the M decoding processing units performs processing for extracting numerical data corresponding to actual data from the head of the distributed partial data each time new partial data is distributed. It is intended to continue as much as possible.

(35) According to a thirty-fifth aspect of the present invention, in the numerical data sequence decoding apparatus according to the thirty-third aspect described above,
Each of the M decoding processing units extracts only numerical data corresponding to actual data for one unit code data from the head of the distributed partial data each time new partial data is distributed. Processing is performed.

(36) In a thirty-sixth aspect of the present invention, in the numerical data string decoding device according to the thirty-third aspect described above,
Among the M decoding processing units, each of the first to (M−1) -th units is 1 from the head of the distributed partial data each time new partial data is distributed. A process for extracting only numerical data corresponding to actual data for one unit code data is performed, and each time the M-th unit distributes new partial data, it starts from the beginning of the distributed partial data. The process for extracting the numerical data corresponding to the actual data is continued as long as normal decryption processing is possible.

(37) According to a thirty-seventh aspect of the present invention, “a structure in which actual data including a bit string having the bit length is arranged following an identification code indicating a combination of a predetermined bit length and a predetermined run length value” is provided. And a numerical sequence corresponding to the actual data after the numerical data indicating 0 is arranged for the number of times corresponding to the run length value, and the total length is a predetermined reference bit length N (where N is 2 Numerical data indicating 0 and individual actual data for an encoded data string formed by arranging a plurality of sets of unit code data (maximum bit length Umax) set to be an integral multiple of the above integer) In the decoding device of the numerical data string for restoring the original data string formed by arranging
A data storage unit for inputting and storing an encoded data sequence to be decoded;
A table storage unit for storing a two-dimensional encoding table indicating a combination of a specific bit length corresponding to each identification code and a specific run length value;
A plurality of M decoding processing units that perform decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax) in parallel,
A data distribution unit that distributes a part of the encoded data sequence stored in the data storage unit as partial data to the M decoding processing units;
A data organization unit that selects a result of the decoding process by the M decoding processing units and generates a decoded data string in which numerical data indicating 0 and numerical data corresponding to individual actual data are arranged;
A data output unit for outputting the generated decrypted data sequence;
Provided,
The data distributing unit counts the bit sequence from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the head of the undecoded unit of the encoded data sequence. , Repeating the process of distributing to the i-th unit (i = 1 to M) until decoding of all parts of the encoded data sequence is completed,
With reference to the two-dimensional encoding table, the M decoding processing units follow the run-length value indicating the number of times the numerical data indicating 0 is listed from the distributed partial data, and the numerical data indicating 0 It has a function to perform the decoding process to extract the numerical data corresponding to the actual data to be processed, and each time new partial data is distributed, it corresponds to the run length value and the actual data from the beginning of the distributed partial data Process to retrieve the numerical data to be
When the processing result is obtained from the M decoding processing units by one parallel processing, the data organization unit first determines the first unit as the first selected unit, and the selected decoding unit performs normal decoding processing. The process of recognizing the last bit performed and determining as another newly adopted unit another unit to which the partial data having the bit immediately after the last bit as the first bit is distributed is performed as much as possible. Numeric data that has been successfully decrypted by the selected unit is collected, and the decrypted data string is generated by arranging the numeric data based on the information collected by one or more parallel processes. Is.

(38) According to a thirty-eighth aspect of the present invention, in the numerical data string decoding device according to the thirty-seventh aspect described above,
Each time the M decoding processing units perform distribution of new partial data, the process for extracting the numerical data corresponding to the run length value and the actual data from the head of the distributed partial data is normally performed. Thus, the decryption process is continued as much as possible.

(39) According to a 39th aspect of the present invention, in the numerical data sequence decoding apparatus according to the 37th aspect described above,
Each time each of the M decoding processing units distributes the new partial data, only the run length value and the numerical data corresponding to the actual data for one unit code data from the head of the distributed partial data. The process for taking out is performed.

(40) According to a 40th aspect of the present invention, in the numerical data string decoding device according to the 37th aspect described above,
Among the M decoding processing units, each of the first to (M−1) -th units is 1 from the head of the distributed partial data each time new partial data is distributed. A process for extracting only numerical data corresponding to run length values and actual data for one unit code data is performed, and each time the M-th unit distributes new partial data, the distributed part The process for extracting the numerical data corresponding to the run length value and the actual data from the beginning of the data is continued as long as normal decoding processing is possible.

(41) According to a 41st aspect of the present invention, in the numerical data string decoding device according to the 37th to 40th aspects described above,
Each of the M decoding processing units executes a process of restoring the original data by arranging the numerical data corresponding to the actual data after arranging the numerical data indicating 0 for the number of times corresponding to the run length value, The restored data is given to the data organization department,
The data organization unit generates a decoded data string by arranging data provided from each decoding processing unit.

(42) According to a forty-second aspect of the present invention, in the numerical data sequence decoding apparatus according to the thirty-seventh to forty-first aspects described above,
Each of the M decoding processing units gives the run length value and the numerical data corresponding to the actual data as they are to the data organization unit,
The data organization unit arranges the numerical data corresponding to the actual data after arranging the numerical data indicating 0 based on the information given from each adopted unit, and arranging the numerical data corresponding to the run-length value. A process of restoring is executed, and a decoded data string is generated by arranging the restored data.

(43) According to a forty-third aspect of the present invention, in the numerical data sequence decoding apparatus according to the thirty-third to forty-second aspects described above,
When a data file including an encoded data string and an encoding table used for encoding processing is given,
The data storage unit performs processing to extract and store the encoded data string from the data file,
The table storage unit extracts the encoding table from the data file and stores it.

(44) According to a 44th aspect of the present invention, in the numerical data string decoding device according to the above 33rd to 42nd aspects,
When a data file including an encoded data string and table specifying information for specifying an encoding table used for encoding processing is given,
The data storage unit performs processing to extract and store the encoded data string from the data file,
The table storage unit performs the process of extracting the table specifying information from the data file and then reading and storing the table specified by the table specifying information from the outside.

(45) A forty-fifth aspect of the present invention is the numerical data string decoding device according to the thirty-third to forty-fourth aspects described above,
A plurality of M decoding processing units such that M ≧ 1 + L / N are provided.

(46) A forty-sixth aspect of the present invention is the numerical data sequence decoding apparatus according to any of the thirty-third to forty-fifth aspects,
Each decoding processing unit has a function of reporting to the data organization unit information obtained by normal decoding processing and a normal processing bit length indicating the number of bits involved in the normal decoding processing,
The data organization unit determines an adopted unit based on the reported normal processing bit length, and generates a decoded data string using the reported information.

(47) According to a 47th aspect of the present invention, in the numerical data sequence decoding apparatus according to the 46th aspect described above,
Each time the data organization unit obtains the processing results from the M decoding processing units by one parallel processing, it recognizes the already-decoding unit by summing the normal processing bit lengths reported from each adopted unit. , Has a function to report this to the data distribution unit,
The data distribution unit recognizes the undecoded unit for the next parallel processing based on the report.

  (48) In a forty-eighth aspect of the present invention, the numerical data string encoding device or decoding device according to the above-described twenty-sixth to forty-seventh aspects is configured by incorporating a program into a computer.

  (49) The forty-ninth aspect of the present invention is the numerical data according to the twenty-eighth aspect described above, in which the numerical data string encoding device according to the twenty-sixth aspect is used as a means for encoding DC component numerical data. The JPEG image compression processing apparatus is configured by using the sequence encoding apparatus as encoding means for the AC component numeric data sequence.

  (50) According to a fifty aspect of the present invention, the above-described numerical data string decoding apparatus according to the thirty-third to thirty-sixth aspects is used as a DC component numerical data decoding means, and the above-described thirty-seventh to forty-second aspects are used. The JPEG image decompression processing apparatus is configured by using the numerical data string decoding device according to the above aspect as the AC component numerical data string decoding means.

(51) According to a fifty-first aspect of the present invention, a numerical data string composed of fixed-length bits is converted into variable-length bits by using an Huffman coding table indicating at least the correspondence between the bit length and the identification code. In a Huffman encoding method for encoding into an encoded data string consisting of:
As a Huffman coding table, when the bit length of the identification code itself is a and the bit length corresponding to the identification code is b, a predetermined reference bit length N (where N is an integer of 2 or more) A table that satisfies the condition of “a + b = k × N” (where k is an arbitrary integer) is used.

(52) According to a fifty-second aspect of the present invention, an arithmetic processing device uses a Huffman coding table indicating a correspondence relationship between at least a bit length and an identification code to convert an encoded data string composed of variable length bits into a fixed length. In the Huffman decoding method for decoding into a numeric data string consisting of bits,
As a Huffman coding table, when the bit length of the identification code itself is a and the bit length corresponding to the identification code is b, a predetermined reference bit length N (where N is an integer of 2 or more) A table that satisfies the condition of “a + b = k × N” (where k is an arbitrary integer) is used.

  (53) According to a fifty-third aspect of the present invention, there is provided data in which actual data comprising a bit string having the bit length is arranged following an identification code indicating the predetermined bit length, and the total length is a predetermined reference bit length N (Where N is an integer equal to or greater than 2), and bit arrangement data configured by arranging a plurality of unit code data (maximum bit length Umax) having different lengths set to be an integral multiple of A data file including a coding table indicating a specific bit length corresponding to each identification code is recorded on a computer-readable information recording medium.

  (54) According to a fifty-fourth aspect of the present invention, there is provided data in which real data consisting of a bit string having the bit length is arranged following an identification code indicating the predetermined bit length, and the total length is a predetermined reference bit length N (Where N is an integer equal to or greater than 2), and bit arrangement data configured by arranging a plurality of unit code data (maximum bit length Umax) having different lengths set to be an integral multiple of A data file including table specifying information for specifying a coding table indicating a specific bit length corresponding to each identification code is recorded on a computer-readable information recording medium.

  (55) According to a 55th aspect of the present invention, “a structure in which an identification code indicating a combination of a predetermined bit length and a predetermined run length value is followed by actual data including a bit string having the bit length is arranged. And a numerical sequence corresponding to the actual data after the numerical data indicating 0 is arranged for the number of times corresponding to the run length value, and the total length is a predetermined reference bit length N (where N is 2 Bit sequence data configured by arranging a plurality of unit code data (maximum bit length Umax) having different lengths set to be an integral multiple of the above integer) and individual identification codes A data file including a two-dimensional encoding table indicating a combination of a specific bit length corresponding to and a specific run length value is recorded on a computer-readable information recording medium Those were Unishi.

  (56) According to a fifty-sixth aspect of the present invention, “a structure in which real data including a bit string having the bit length is arranged following an identification code indicating a combination of a predetermined bit length and a predetermined run-length value” is provided. And a numerical sequence corresponding to the actual data after the numerical data indicating 0 is arranged for the number of times corresponding to the run length value, and the total length is a predetermined reference bit length N (where N is 2 Bit sequence data configured by arranging a plurality of unit code data (maximum bit length Umax) having different lengths set to be an integral multiple of the above integer) and individual identification codes A computer-readable data file including table specifying information for specifying a two-dimensional encoding table that indicates a combination of a specific bit length corresponding to and a specific run length value An information recording is obtained so as to record on the medium.

  (57) In a 57th aspect of the present invention, a data file output by the numerical data string encoding method according to the sixth or seventh aspect described above is recorded on a computer-readable information recording medium. It is a thing.

(58) A 58th aspect of the present invention is a table used in an encoding method for encoding a numeric data string using a variable-length bit string,
For a plurality of bit lengths within a predetermined range, the correspondence between individual bit lengths and unique identification codes corresponding to the bit lengths is shown.
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. The code does not exist in this table, and when the bit length corresponding to the target identification code is b, “a + b = N” is a predetermined reference bit length N (where N is an integer of 2 or more). A table that satisfies the condition of “k × N” (where k is an arbitrary integer) is recorded on a computer-readable information recording medium.

(59) A 59th aspect of the present invention is a table used in an encoding method for encoding a numeric data string using a variable-length bit string,
For a plurality of bit lengths within a predetermined range and a plurality of run length values within a predetermined range, each combination of individual bit lengths and individual run length values, and a unique identification code corresponding to the combination, Is shown,
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. The code does not exist in this table, and when the bit length corresponding to the target identification code is b, “a + b = N” is a predetermined reference bit length N (where N is an integer of 2 or more). A table that satisfies the condition of “k × N” (where k is an arbitrary integer) is recorded on a computer-readable information recording medium.

  In the encoding of numerical data according to the present invention, by adding an identification code having information indicating the bit length of the actual data to the beginning of the actual data representing the numerical data itself using a variable-length bit string, Unit code data having information indicating the specific numerical data itself is generated. Moreover, when the bit length of the identification code itself is a and the bit length of the actual data is b, “a + b = k ×” with respect to a predetermined reference bit length N (where N is an integer of 2 or more). N ”(where k is an arbitrary integer) is satisfied.

  For this reason, since the bit length of the unit code data is always an integer multiple of N, the boundary of the processing unit of the encoded data string is always a bit position of an integer multiple of N from the beginning. Therefore, it is possible to divide the encoded data string into a plurality of partial data at bit positions that are integer multiples of N from the beginning, and perform decoding by parallel processing using a plurality of decoding processing units. Since the value of k is an arbitrary integer, the bit position that is an integer multiple of N is not necessarily the correct position as the boundary of the processing unit, but the boundary of the processing unit is always the bit position that is an integer multiple of N. Therefore, a correct decoded data string can be obtained by selecting and arranging only the processing results of the units that have been decoded in the correct processing unit among the plurality of decoding processing units.

  Thus, it is possible to perform special encoding that enables parallel processing at the stage of decoding while encoding a numeric data string composed of fixed-length bits using a variable-length bit string. In addition, the encoded data string created by the encoding can be decoded by parallel processing using a plurality of decoding processing units.

It is a figure which shows an example of the numerical data expressed by the fixed length bit. It is a figure which shows the fixed length bit sequence expressing the numerical data shown in FIG. It is a figure which shows the variable length bit sequence obtained by deleting redundant 0 from the fixed length bit sequence shown in FIG. It is a figure which shows the state which inserted the information (circle number) which shows bit length in the variable length bit sequence shown in FIG. It is a figure which shows the basic structure of the unit code data which comprises the data encoded using the bit string of variable length. FIG. 3 is a diagram showing a process of encoding the numerical data string expressed by the fixed-length bit string shown in FIG. 2 using a fixed-length encoding table. FIG. 3 is a diagram showing a process of encoding the numerical data string expressed by the fixed-length bit string shown in FIG. 2 using a variable-length encoding table. FIG. 3 is a diagram illustrating a process of encoding the numerical data string expressed by the fixed-length bit string shown in FIG. 2 using a Huffman encoding table. It is a figure which shows the process which encodes the numerical data sequence expressed with the fixed length bit sequence shown in FIG. 2 using the encoding table which concerns on this invention. It is a 1st figure which shows the principle which decodes the encoding data sequence shown in FIG.9 (c) by the parallel process by eight decoding process units using the decoding method which concerns on this invention. It is the 2nd figure which shows the principle which decodes the encoding data sequence shown in FIG.9 (c) by the parallel process by eight decoding process units using the decoding method which concerns on this invention. It is the 3rd figure which shows the principle which decodes the encoding data sequence shown in FIG.9 (c) by the parallel process by eight decoding process units using the decoding method which concerns on this invention. It is the 4th figure which shows the principle which decodes the encoding data sequence shown in FIG.9 (c) by the parallel process by eight decoding process units using the decoding method which concerns on this invention. It is a flowchart which shows the basic procedure of the encoding method of the numerical data sequence which concerns on this invention. It is a block diagram which shows an example of the structure of the encoding data file produced with the encoding method of the numerical data sequence which concerns on this invention. It is a block diagram which shows another example of the structure of the encoding data file produced with the encoding method of the numerical data sequence which concerns on this invention. It is a flowchart which shows the basic procedure of the decoding method of the numerical data sequence which concerns on this invention. It is a block diagram which shows the basic composition of the encoding apparatus of the numerical data sequence which concerns on this invention. It is a block diagram which shows the basic composition of the decoding apparatus of the numerical data sequence which concerns on this invention. It is a figure which shows an example of another numerical data sequence used as the object of an encoding. It is a figure which shows the process of implementing the encoding method using the one-dimensional encoding table based on this invention with respect to the numerical data sequence shown in FIG. It is a figure which shows the basic principle of the encoding method using the two-dimensional encoding table which concerns on this invention. It is a figure which shows the process of implementing the encoding method using the two-dimensional encoding table which concerns on this invention with respect to the numerical data sequence shown in FIG. It is a flowchart which shows the basic procedure of the encoding method using the two-dimensional encoding table which concerns on this invention. It is a block diagram which shows the structure of the compression / decompression processing apparatus for a general JPEG image. It is a top view which shows the pixel arrangement | sequence which comprises the 8x8 pixel block after quantization at the time of performing the compression of a JPEG system. It is a top view which shows an example of the pixel value distribution of the pixel block after the quantization used as the object of the compression process of a JPEG system. It is a figure which shows the numerical data of DC component and AC component extracted from the pixel block shown in FIG. It is a figure which shows an example of the encoding table for DC components (one-dimensional encoding table) which concerns on this invention. It is a figure which shows the result of having encoded the DC component shown in FIG. 28 using the table shown in FIG. It is a figure which shows an example of the encoding table for AC components (two-dimensional encoding table) which concerns on this invention. It is a figure which shows the process of encoding the AC component shown in FIG. 28 using the table shown in FIG. It is a figure which shows the result of having encoded the AC component shown in FIG. 28 using the table shown in FIG. It is a 1st figure which shows the principle which decodes the encoding data sequence shown in FIG. 33 by the parallel process by seven decoding process units using the decoding method which concerns on this invention. It is the 2nd figure which shows the principle which decodes the encoding data sequence shown in FIG. 33 by the parallel process by seven decoding process units using the decoding method which concerns on this invention. It is a block diagram which shows the basic composition of the encoding apparatus using the Huffman encoding table which concerns on this invention. It is a figure which shows an example of the frequency count result for creating a one-dimensional Huffman coding table. It is a figure which shows the specific method of producing the one-dimensional Huffman encoding table based on this invention. It is a figure which shows an example of the frequency tabulation result (luminance component and color difference component) for creating a two-dimensional Huffman encoding table. FIG. 32 is a diagram showing an example (for luminance component) of a two-dimensional Huffman coding table created by modifying the table shown in FIG. 31. FIG. 32 is a diagram showing another example (for color difference components) of a two-dimensional Huffman coding table created by modifying the table shown in FIG. 31. 5 is a graph showing parameters to be considered when setting a reference bit length N. It is a figure which shows the modification of the decoding principle shown in FIG. It is a figure which shows the modification of the decoding principle shown in FIG. It is a figure which shows the modification of the decoding principle shown in FIG. It is a figure which shows the 1st reference table for decoding produced from the encoding table shown in FIG. It is a figure which shows the 2nd reference table for decoding produced from the encoding table shown in FIG. FIG. 48 is a diagram showing the principle of a decoding process using the first and second decoding reference tables shown in FIGS. 46 and 47.

  Hereinafter, the present invention will be described based on the illustrated embodiments.

<<< §1. Basic principle of conventional encoding / decoding method >>
The present invention relates to a technique for encoding a numeric data string composed of fixed-length bits using a variable-length bit string and performing decoding to restore the encoded value. Therefore, the basic principle of a conventional encoding / decoding method that involves conversion between such a fixed-length bit string and a variable-length bit string will be briefly described.

  Consider numerical data strings D1, D2, D3, D4, D5,... Expressed by fixed-length bits as shown in FIG. Here, each of these numerical data is a value in the range of 0 to 255 that can be expressed by 8 bits. Specifically, in decimal notation, 28, 251, 1, 13, 3,. Let's assume the value .. In this case, in the binary notation, as shown in the table of FIG.

  FIG. 2 is a diagram showing a fixed-length bit string representing the numerical data shown in FIG. Any numerical data is represented by an 8-bit bit string regardless of the size. For this reason, the data delimiter always appears in an 8-bit cycle, and random access to desired numerical data is possible, which is suitable for arithmetic processing by the CPU. However, 0 at the beginning of each numerical data is a redundant bit. For example, in the case of the numerical data D3, the actual data portion indicating the original numerical value is only “1” at the end, and the seven “0” s added to the head are redundant bits.

  FIG. 3 is a diagram showing a variable-length bit string obtained by deleting redundant 0 from the fixed-length bit string shown in FIG. In any numerical data, the leading 0 is deleted and only the bit string indicating the actual data remains. For example, the numerical data D3 is represented by only 1-bit actual data “1”. In this way, the data capacity can be reduced by expressing the numerical data string expressed in the fixed-length bit string as the variable-length bit string.

  However, individual numerical data cannot be extracted from the variable-length bit string shown in FIG. This is because the delimiter information of each numerical data is lost, and it is unclear where this bit string is delimited and handled as one numerical value. In FIG. 2 and FIG. 3, for convenience of explanation, a bit string indicating one numerical value data is surrounded by a rectangular frame, but actually, such a rectangular frame does not exist. Therefore, in the case of the fixed-length bit string shown in FIG. 2, it is possible to extract individual numerical data by dividing the bit string in units of 8 bits. However, in the case of the variable-length bit string shown in FIG. , Individual numerical data cannot be recognized.

  Eventually, when converting a fixed-length bit string into a variable-length bit string, it is necessary to add some information indicating a delimiter of numerical data. Therefore, usually, a method of adding information indicating the bit length of the actual data to the head of the actual data indicating each numerical value is employed. FIG. 4 is a diagram illustrating a state in which information indicating the bit length is inserted into the variable-length bit string illustrated in FIG. The information indicated by the circled numbers in the figure is an identification code indicating the bit length of the subsequent actual data. For example, the head identification code C1 (circle numeral 5) indicates that the bit length of the subsequent actual data D1 is “5”, and the subsequent identification code C2 (circle numeral 8) is the subsequent actual data D2. This indicates that the bit length of “8” is “8”.

  After all, the data bit string shown in FIG. 4 is a sequence of unit code data U having a basic structure as shown in FIG. That is, the unit code data U is composed of an identification code C and subsequent real data D (variable length bit string), and the identification code C is a code indicating the bit length b of the subsequent actual data D. Become. In order to extract each numerical data from the data bit string shown in FIG. 4, first, the portion of the head identification code C1 is analyzed to recognize that the bit length of the subsequent actual data D1 is “5”. What is necessary is just to take out 5-bit information as the data D1. Next, the part of the identification code C2 is analyzed to recognize that the bit length of the subsequent actual data D2 is “8”, and 8-bit information is extracted as the actual data D2. The same applies hereinafter.

  As shown in FIG. 5, the unit code data U is composed of a part of an identification code C having a bit length a and a part of actual data D having a bit length b. For convenience of explanation, the identification code C portion and the actual data D portion are shown surrounded by a rectangular frame. However, in reality, such a rectangular frame does not exist. Therefore, it is necessary to be able to recognize the separation position between the identification code C portion and the identification code D portion by some method.

  The simplest method is to set the bit length a of the identification code C to a fixed length. For example, if the bit length a is fixed to 3 bits, the first 3 bits of the unit code data U are always the identification code C, so that the separation between the identification code C and the actual data D is clear. Therefore, if the bit length b of the subsequent actual data D is recognized based on the 3-bit identification code C, the actual data D can be correctly extracted.

  As the identification code C, a digital value itself corresponding to the bit length b can be used. For example, as the identification code C indicating the bit length b = “5”, the 3-bit bit string “101” indicating “5” can be used as it is. However, any bit string may be used for the identification code C as long as the correspondence between the identification code C and the bit length b is clear.

  FIG. 6 is a diagram showing a process of encoding the numerical data string expressed by the fixed-length bit string shown in FIG. 2 using a fixed-length encoding table. FIG. 6 (a) is the same diagram as FIG. 4, and shows a state in which information (circle numerals) indicating the bit length is inserted into the variable length bit string shown in FIG. FIG. 6B is a fixed-length encoding table that shows the correspondence between the identification code C and the bit length b. In this example, the identification code C is not a digital value having a corresponding bit length b. For example, a 3-bit bit string indicating the bit length b = “1” is “001”, but in the illustrated table, the identification code C corresponding to the bit length b = “1” is “000”. . Nevertheless, since it can be recognized that the bit length b corresponding to the identification code C “000” is “1” by referring to this table, no trouble occurs.

  FIG. 6 (c) shows the unique code defined in the fixed length coding table of FIG. 6 (b) in each identification code C1, C2,... Indicating the bit length of the circled numbers in FIG. The encoded data string obtained by applying the identification code C is shown. If the encoded data sequence shown in FIG. 6 (c) and the fixed-length encoding table shown in FIG. 6 (b) are used, the original fixed-length bit numeric data sequence shown in FIG. 2 can be restored. .

  That is, for the identification code C1 “100” in the first 3 bits of the encoded data string in FIG. 6C, the corresponding bit length b = “5” is obtained by referring to the table in FIG. 6B. Therefore, if the subsequent 5-bit data “11100” is recognized as the actual data D1, the 8-bit data “00011100” can be restored. Subsequently, referring to the table of FIG. 6B for the identification code C2 “111” in the ninth to eleventh bits of the encoded data string of FIG. 6C, the corresponding bit length b = “8” ”Is obtained, and the subsequent 8-bit data“ 11111011 ”can be recognized as the actual data D2. The same applies hereinafter.

  In the table of FIG. 6B, eight kinds of bit lengths b = 1 to 8 can be indicated by the identification code C fixed to 3 bits. This assumes that the bit length of actual data is a minimum of 1 bit and a maximum of 8 bits. As a result, in the example shown in FIG. 6, the actual data D has a variable length of 1 to 8 bits, but the identification code C has a fixed length of 3 bits. When defining the bit length b = 0 of the real data (for example, the real data of the numerical data “00000000” is not a one-digit bit “0” but a zero-digit virtual data with a bit length of 0, That is, in the case where the bits representing actual data are expressed without being arranged), it is also necessary to define the identification code C corresponding to the bit length b = 0.

  On the other hand, a method of making the bit length a of the identification code C variable is also known. FIG. 7 is a diagram showing a process of encoding the numerical data string expressed by the fixed-length bit string shown in FIG. 2 using a variable-length encoding table. FIG. 7 (a) is the same diagram as FIG. 4, and shows a state in which information (round numerals) indicating the bit length is inserted into the variable length bit string shown in FIG. FIG. 7B is a variable length coding table, which shows the correspondence between the variable length identification code C and the bit length b. In the fixed length coding table shown in FIG. 6B, the identification code C has a fixed length of 3 bits, whereas in the variable length coding table shown in FIG. It has a variable length of 1 to 7 bits.

  FIG. 7 (c) shows the unique code defined in the variable length coding table of FIG. 7 (b) in each identification code C1, C2,... The encoded data string obtained by applying the identification code C is shown. If the encoded data sequence shown in FIG. 7 (c) and the variable length encoding table shown in FIG. 7 (b) are used, the original fixed-length bit numerical data sequence shown in FIG. 2 can be restored. . However, since the identification code has a variable length, it is necessary to check whether there is a matching code by referring to the variable length coding table while checking the encoded data string bit by bit from the beginning. .

  Specifically, first, the presence or absence of a matching identification code C is examined for bit “1” of the first bit of the encoded data string of FIG. There is no matching identification code in the table of FIG. Then, next, the presence or absence of a matching identification code C is examined for the bit string “11” of the first and second bits, but there is no matching identification code. Further, the presence or absence of a matching identification code C is checked for the bit string “111” of the first to third bits, but there is no matching identification code. In this way, when the bit string to be matched is extended one bit at a time, a matching identification code is found for the bit string “11110” of the first to fifth bits for the first time. Thus, it can be recognized that the part of the 5-bit bit string “11110” from the top is the identification code C.

  According to the table of FIG. 7B, since the bit length b corresponding to the identification code “11110” is “5”, the bit string “11100” of the sixth to tenth bits can be extracted as the actual data D1, The 8-bit data “00011100” can be restored.

  Subsequently, the above-described match determination process is continued from the 11th bit of the encoded data string of FIG. First, the bit “1” of the eleventh bit is checked for the presence of a matching identification code C, but no matching identification code exists. Then, next, the presence or absence of a matching identification code C is examined for the bit string “11” of the 11th to 12th bits, but there is no matching identification code. In this way, when the bit string to be matched is extended bit by bit, a matching identification code is found for the bit string “1111111” of the 11th to 17th bits for the first time. Thus, it can be recognized that the portion of the 7-bit bit string “1111111” is the identification code C.

  According to the table of FIG. 7B, since the bit length b corresponding to the identification code “1111111” is “8”, the bit string “11111011” of the 18th to 25th bits can be extracted as the actual data D2. The same applies hereinafter.

  As described above, when the identification code C is a variable length code, a condition is imposed on the identification code constituting the table. That is to say, “Even when focusing on any identification code in the table, when the bit length of the target identification code itself is a, the portion of the a bit from the beginning is the same as the target identification code. No such identification code exists in this table ".

  For example, paying attention to the identification code “0” in the table of FIG. 7B, since the bit length a = 1, the above condition is “There is no other identification code in which the first 1-bit portion is 0”. It becomes a condition. In fact, there are no other identification codes starting with 0 in this table. Similarly, paying attention to the identification code “10” in the table of FIG. 7B, since the bit length a = 2, the above condition is “There is no other identification code in which the first 2 bits are 10.” It becomes the condition. In fact, there are no other identification codes starting with 10 in this table.

  The reason why such a condition is necessary can be easily understood by considering the algorithm of the match determination process described above. That is, if the condition is not satisfied, the identification code is erroneously recognized. For example, even if different identification codes “100”, “101”, “1000”, etc. starting with the same “10” as the identification code “10” exist in the same table, the match determination process for the bit string “10” is performed. Since the “match” determination is made, the match determination for the identification codes “100”, “101”, “1000”, etc. is not performed.

  By the way, comparing the encoded data sequence shown in FIG. 7 (c) with the encoded data sequence shown in FIG. 6 (c), it can be seen that the total bit length of the former is larger than that of the latter. This is because the identification code C is always 3 bits in the fixed-length coding table shown in FIG. 6B, whereas in the variable-length coding table shown in FIG. This is because although the length may be one bit, it may require 7 bits in some cases. Therefore, in practice, the appearance frequency of the bit length b for each actual data is aggregated, and the higher the appearance frequency of the actual data bit length b, the more the identification code with the shorter bit length a is associated with the code. Use a conversion table. Thus, the variable length coding table created in consideration of the appearance frequency is generally called a Huffman coding table, and coding using this Huffman coding table is called Huffman coding. Yes.

  FIG. 8 is a diagram showing a process of encoding the numerical data string expressed by the fixed-length bit string shown in FIG. 2 using the Huffman encoding table. FIG. 8A is the same diagram as FIG. 4 and shows a state in which information (round numerals) indicating the bit length is inserted into the variable length bit string shown in FIG. FIG. 8B is a Huffman coding table, which is a variable length coding table showing the correspondence between the variable length identification code C and the bit length b. Here, for convenience of explanation, the appearance frequency is shown in the broken line column on the left side of the Huffman coding table. This appearance frequency indicates the appearance frequency of the bit length b for each actual data of the numerical data to be encoded (in the example shown here, the numerical data D1, D2,... Shown in FIG. 2). It is. In the case of the illustrated example, the appearance frequency of the bit length b = “4” is “685”, which is the first.

  The illustrated table shows the bit lengths b sorted in the order of appearance frequency. Here, looking at the column of the identification code C, it can be seen that the identification codes C are also sorted in the shortest order. That is, the higher the appearance frequency of the bit length b, the more the identification code having the shorter bit length a is associated. When encoding using such a Huffman encoding table is performed, the shorter identification code C is used more frequently, so that the total bit length of the obtained encoded data string can be shortened. The data capacity can be reduced. For example, the 7-bit identification code C such as “1111110” and “1111111” in the table of FIG. 8B is used with a very low frequency, and the presence of these long identification codes increases the total bit length. The impact is small.

  FIG. 8 (c) shows the unique code defined in the Huffman coding table of FIG. 8 (b) in each identification code C1, C2,... An encoded data string obtained by applying the identification code C is shown. If the encoded data sequence shown in FIG. 8 (c) and the Huffman encoding table shown in FIG. 8 (b) are used, the original fixed-length bit numerical data sequence shown in FIG. 2 can be restored. Is exactly the same as the example of FIG. In addition, it is exactly the same as the example in FIG. 7 in that while checking the encoded data string bit by bit from the head, the Huffman encoding table is referenced to check whether there is a matching code. .

  Therefore, even in this Huffman coding table, “when any identification code in the table is focused, when the bit length of the targeted identification code itself is a, the portion of the a bit from the head is identified as the focused identification. There is no change in the necessity of the condition that “another identification code that is identical to the code does not exist in this table”. The feature of the Huffman coding table is that “the higher the appearance frequency of the bit length b of the actual data is, the more the identification code having the shorter bit length a is associated”. This is not different from the general variable length coding table described. In other words, the Huffman coding table shown in FIG. 8 (b) is shown in FIG. 7 (b) so that as the appearance frequency of the bit length b increases, an identification code having a shorter bit length a is associated. It can be said that the table is obtained by performing an operation of exchanging the identification code C portions of the variable length coding table shown.

  Comparing the encoded data sequence shown in FIG. 8 (c) with the encoded data sequence shown in FIG. 7 (c), it can be seen that the total bit length is smaller in the former than in the latter. Although only five numerical data portions are shown in the figure, the bit length of each numerical data appears with an appearance frequency as shown in the broken line column of FIG. 8 (b). Therefore, the effect of reducing the data capacity when using the Huffman coding table becomes more remarkable. Patent Documents 1 and 2 listed above disclose a technique for compressing image data by the JPEG method using such a Huffman coding table.

<<< §2. The origin of the idea of the present invention >>>
Now, in order to return the encoded data string (variable length bits) created by the method described in §1 to the original numerical data (fixed length bits) suitable for arithmetic processing by the CPU, it is necessary to perform decoding. There is. However, the encoded data consisting of variable-length bit strings does not have a fixed bit position as a delimiter, so the boundaries of the processing units are unclear. In the conventional general method, decoding is performed by parallel processing. I can't.

  For example, in the encoded data sequence shown in FIG. 6 (c), although the identification code C portion is fixed to 3 bits, the actual data D portion has a variable length, so the boundary of each unit code data U is It can be recognized for the first time by performing the decoding process sequentially from the beginning of the data string. Actually, the boundaries of the unit code data U1, U2, U3, U4, and U5 are irregular, and the boundaries cannot be recognized unless this bit string is analyzed in order from the top. This means that when decoding the encoded data string shown in FIG. 6 (c), decoding processing must be performed in order from the top using one decoding processing unit. For this reason, as described above, it takes time for the decoding process, and in particular, in the case of video data or the like for which a real-time display process is required, problems such as hindering smooth reproduction occur.

  Such circumstances include the encoded data sequence shown in FIG. 7C (obtained by the encoding process using the variable length encoding table) and the encoded data sequence shown in FIG. 8C (Huffman). The same applies to (obtained by the encoding process using the encoding table).

  As a technique for dealing with such a problem, the present inventor has been able to obtain the following idea. Now, when decoding the encoded data shown in FIG. 8 (c), it is considered that this data string is divided at a predetermined position, and individual partial data is given to a plurality of decoding processing units to perform parallel processing. Like. If parallel processing by a plurality of decoding processing units can be realized, the time required for decoding processing can be shortened accordingly, and smooth video reproduction and the like can be performed.

  However, in order for each decoding processing unit to perform correct decoding processing, it is necessary to cut out each partial data at the correct position. Specifically, it is necessary to divide at the boundary of each unit code data U1, U2, U3, U4, U5. However, since the bit length of the actual data D constituting the unit code data U is variable, the boundary of the unit code data U is indeterminate. Therefore, the inventor of the present application has obtained the first idea that the uncertainty of the bit length of the actual data D can be complemented by the bit length of the identification code C.

  As shown in FIG. 5, the bit length of the unit code data U is the sum “a + b” of the bit length a of the identification code C itself and the bit length b of the actual data D. Moreover, the identification code C to be used is determined based on the bit length b of the subsequent actual data D. Therefore, the inventor of the present application defines the identification code C by a variable length coding table as shown in FIGS. 7B and 8B, and sets the bit length a of the identification code C itself as follows: It was considered that if the bit length b corresponding to the identification code C was determined, the sum of bit lengths “a + b” could be made constant.

  For example, if the bit length of the unit code data U shown in FIG. 5 is set to a fixed value N and operation that always satisfies “a + b = N” is possible, the boundary of the unit code data U is always N bits. Therefore, if the partial data is cut out at the position of the N-bit period, the head of each partial data coincides with the head of the unit code data U, and each decoding processing unit performs correct decoding. Processing can be performed.

  However, when a variable length coding table that always satisfies “a + b = N” is actually designed, the higher the appearance frequency of the bit length b, the more the Huffman coding table is associated with an identification code having a shorter bit length a. It becomes impossible to apply to. For example, consider modifying the variable length coding table shown in FIG. 7B so that “a + b = N” always holds. Here, for example, if N = 9 is fixed, an identification code C having a bit length a such that a = 9−b may be placed in each column of the table. Therefore, the identification code corresponding to the bit length b = 1 is a code having a length of 8 bits, the identification code corresponding to the bit length b = 2 is a code having a length of 7 bits, and the bit length b = 3 The corresponding identification code is a code having a length of 6 bits,..., And the identification code corresponding to a bit length b = 8 is a code having a length of 1 bit. It is possible to create a long coding table.

  However, when the Huffman coding table is created by performing replacement such that an identification code having a shorter bit length a is associated as the appearance frequency of the bit length b is higher, the condition “a + b = N” is not necessarily satisfied. It will disappear. After all, the variable length coding table that satisfies the condition “a + b = N” has a remarkably limited degree of freedom in the correspondence relationship between the bit length b and the identification code C, and can be applied to the Huffman coding table considering the appearance frequency. It cannot be used at all, and must be extremely low in practical use.

  Therefore, the inventor of the present application has a coding table that satisfies a condition of “a + b = k × N” (where k is an arbitrary integer) with respect to a predetermined reference bit length N (where N is an integer of 2 or more). As a result, the second idea of giving a certain degree of freedom to the bit length a of the identification code C has been obtained. Under the above conditions, the bit length a can be increased or decreased by the unit of the reference bit length N by adjusting the value of k. Therefore, the bit length a can be set according to the appearance frequency of the bit length b. it can.

  However, if the condition of “a + b = k × N” is set for the bit length “a + b” of the unit code data U, the bit length of the unit code data U does not become a fixed value. Therefore, the problem that the boundary of the unit code data U is not fixed comes up again. However, if the above condition is set, the boundary of the unit code data U does not become irregular at all, but always becomes a position that is an integral multiple of the reference bit length N. Therefore, when performing decoding, the inventor of the present application creates partial data by dividing an encoded data string at a position that is an integral multiple of the reference bit length N for the time being, and each partial data is divided into a plurality of decoding processing units. Given that the third idea is that if the decoding is performed in parallel and only the processing result of the unit where the correct decoding is performed is adopted, the correct decoded data string can be obtained. is there.

  Since the value of k is an arbitrary integer, a bit position that is an integer multiple of N is not necessarily a correct position as a boundary of the unit code data U, but the boundary of the unit code data U is always an integer multiple of N. At the bit position. Therefore, some of the plurality of decoding processing units start the wrong decoding process in the middle of the unit code data U, but some others are correct from the beginning of the unit code data U. The decoding process is started. Finally, if only the correct decoding process result is adopted and the wrong decoding process result is discarded, the erroneous decoding process is wasted, but the effect of shortening the time required for decoding by parallel processing is can get.

  Thus, according to the present invention, while encoding a numerical data string composed of fixed-length bits using a variable-length bit string, a plurality of decoding processing units are used for the encoded data at the decoding stage. Decoding can be performed by parallel processing. In the following §3, the basic principle of the present invention will be described in detail with specific examples.

<<< §3. Basic principle of encoding method according to the present invention >>
FIG. 9 is a diagram showing a process of encoding the numerical data string expressed by the fixed-length bit string shown in FIG. 2 using the encoding table according to the present invention. FIG. 9 (a) is the same diagram as FIG. 4, and shows a state in which the information (circle numerals) indicating the bit length is inserted into the variable length bit string shown in FIG. FIG. 9 (b) is an encoding table used in the present invention.

  This table is not a Huffman coding table because the appearance frequency of the bit length b is not taken into consideration, but is a variable length coding table showing the correspondence between the variable length identification code C and the bit length b. Here, for convenience of explanation, the bit length a of the identification code C itself and the bit length “a + b” of the unit code data U including the identification code C are shown in the broken line column on the right side of the encoding table (this The content of the broken line column is shown for convenience of explanation and is not a part of this encoding table).

  In the table of FIG. 9B, identification codes C corresponding to nine bit lengths of b = 0 to 8 are defined. In each encoding table described in §1, corresponding identification codes C are defined for eight bit lengths of b = 1 to 8, respectively. However, in the table of FIG. 9B, b = In the case of 0, the identification code is defined. This is because the embodiment described below adopts a method of defining the bit length b = 0 of actual data. Specifically, the real data of the numerical data “00000000” is not a single-digit bit “0”, and 0-digit virtual data having a bit length of 0, that is, a bit that substantially indicates the actual data is not arranged. (In this case, the unit code data U is substantially composed only of bits constituting the identification code C).

  The table of FIG. 9B is an encoding table that satisfies the condition “a + b = k × N” described in §2. Specifically, in this example, the reference bit length N is set to 4 and the value of the integer k is 1, 2, 3, or 4. For example, in the first row of the table, a 4-bit code “1000” is shown as the identification code C indicating the bit length b = 0. Here, the bit length b = 0 is used when the actual data of the numerical data “00000000” is represented by a virtual bit having a length of 0 bits as described above, and is a bit that substantially constitutes the actual data D. Does not exist. Accordingly, the bit length “a + b” of the unit code data U in this case is 4.

  On the other hand, in the second row of the table, a 3-bit code “010” is shown as an identification code C indicating the bit length b = 1. In this case, the bit length “a + b” of the unit code data U is also 4. In the third row of the table, a 2-bit code “00” is shown as an identification code C indicating the bit length b = 2. In this case, the bit length “a + b” of the unit code data U is also 4. The fourth row of the table shows a 5-bit code “10100” as the identification code C indicating the bit length b = 3. In this case, the bit length “a + b” of the unit code data U is 8. The same applies to the following. Finally, the 9th row of the table shows an 8-bit code “10111010” as the identification code C indicating the bit length b = 8. In this case, the bit length “a + b” of the unit code data U is 16.

  After all, when encoding is performed using the encoding table shown in FIG. 9B, the bit length “a + b” of the unit code data U is any of 4, 8, 12, and 16. That is, it is always an integer multiple of the reference bit length N = 4, and the maximum bit length Umax = 16. Of course, this encoding table is basically a variable-length encoding table, similar to the table shown in FIG. 7 (b), so that any attention can be paid to any identification code in the table. When the bit length of the identification code itself is a, the condition that another identification code in which the a-bit portion from the head is the same as the target identification code does not exist in this table is also satisfied.

  FIG. 9 (c) shows a unique identification defined in the encoding table of FIG. 9 (b) in each identification code C1, C2,... An encoded data string obtained by applying the code C is shown. If the encoded data sequence shown in FIG. 9 (c) and the encoding table shown in FIG. 9 (b) are used, the original fixed-length bit numerical data sequence shown in FIG. 2 can be restored. This is exactly the same as the example of FIG. That is, when decoding is performed, the encoded data string is checked bit by bit from the head while referring to the encoding table to check whether a matching code exists.

  Specifically, first, the presence or absence of a matching identification code C is checked for the bit “0” of the first bit of the encoded data string in FIG. There is no matching identification code in the table of FIG. Then, next, the presence or absence of a matching identification code C is examined for the bit string “01” of the first and second bits, but there is no matching identification code. Further, when the presence or absence of a matching identification code C is checked for the bit string “011” of the first to third bits, an identification code corresponding to the bit length “5” is finally found. Therefore, it can be recognized that the portion of the 3-bit bit string “011” from the top is the identification code C, and the subsequent 5-bit bit string “11100” can be extracted as the actual data D1, and the 8-bit data “ “00011100” can be restored.

  Subsequently, the same match determination process is continued from the ninth bit of the encoded data string of FIG. 9 (c). First, for the bit “1” of the ninth bit, the presence or absence of a matching identification code C is checked, but there is no matching identification code. Then, next, the presence or absence of a matching identification code C is examined for the bit string “10” of the ninth to tenth bits, but there is no matching identification code. In this way, when the bit string to be matched is extended bit by bit, a matching identification code is found for the bit string “10111010” of the 9th to 16th bits for the first time. Thus, it can be recognized that the portion of the bit string “10111010” is the identification code C. According to the table of FIG. 9B, since the bit length b corresponding to the identification code “10111010” is “8”, the bit string “11111011” of the 17th to 24th bits can be extracted as the actual data D2.

  Next, when the same match determination process is continued from the 25th bit of the encoded data string of FIG. 9 (c), the bit string “010” of the 25th to 27th bits is matched for the first time. The code is found. Thus, it can be recognized that the portion of the bit string “010” is the identification code C. According to the table of FIG. 9 (b), since the bit length b corresponding to the identification code “010” is “1”, the bit “1” of the 28th bit can be taken out as the actual data D3, and 8 bits Data “00000001” can be restored.

  Subsequently, when the same match determination process is continued from the 29th bit of the encoded data string of FIG. 9 (c), the bit string “1001” of the 29th to 32nd bits is matched for the first time. The code is found. Thus, it can be recognized that the portion of the bit string “1001” is the identification code C. According to the table of FIG. 9B, since the bit length b corresponding to the identification code “1001” is “4”, the bit “1101” of the 33rd to 36th bits can be extracted as the actual data D4. The 8-bit data “00001011” can be restored.

  Finally, when the same match determination process is continued from the 37th bit of the encoded data string of FIG. 9 (c), the bit string “00” of the 37th to 38th bits is matched for the first time. The code is found. Thus, it can be recognized that the portion of the bit string “00” is the identification code C. According to the table of FIG. 9B, since the bit length b corresponding to the identification code “00” is “2”, the bit “11” of the 39th to 40th bits can be extracted as the actual data D5. The 8-bit data “00000011” can be restored.

  Note that the encoding table shown in FIG. 9 (b) is “a + b” even if two identification codes whose corresponding bit length b is an integer multiple of N (N = 4 in this example) are interchanged. = K × N ”remains maintained. For example, even if the identification code “00” corresponding to the bit length b = “2” and the identification code “101100” corresponding to the bit length b = “6” are interchanged, the above condition is maintained. (The value of k changes.) Similarly, for example, even if the identification code “1001” corresponding to the bit length b = “4” and the identification code “10111010” corresponding to the bit length b = “8” are interchanged, the above condition is maintained. (K value changes). By performing such replacement, it is possible to create a Huffman coding table in which an identification code having a shorter bit length a is associated with an increase in the appearance frequency of the bit length b.

<<< §4. Basic principle of decoding method according to the present invention >>
In §3, the encoding method according to the present invention and the specific encoded data sequence shown in FIG. 9 (c) created by the encoding method are sequentially used from the top using one decoding processing unit. The procedure for decoding while processing is described. However, when decoding using a single decoding processing unit is assumed, the particular merit of performing the encoding processing shown in FIG. 9 is not utilized. Actually, the encoded data sequence shown in FIG. 9 (c) has a slightly larger data capacity than the encoded data sequence shown in FIG. 7 (c), and the merit of further reducing the data capacity cannot be obtained. A unique advantage of performing the encoding process shown in FIG. 9 is that decoding by parallel processing becomes possible, and the time required for decoding can be shortened. Hereinafter, this merit will be described while showing a specific decoding processing procedure.

  The data lengths of the unit code data U1, U2, U3, U4, and U5 constituting the encoded data string in FIG. 9 (c) are 8 bits, 16 bits, 4 bits, 8 bits, and 4 bits, as shown in the figure. Both are integer multiples of the reference bit length N = 4. Therefore, if this encoded data string is divided every 4 bits, the division is not necessarily the boundary of the unit code data U, but the boundary of the unit code data U is always at the position of the division. It will be. Therefore, if a plurality of partial data is generated by shifting the delimiter position by 4 bits from the beginning, and these are respectively given to a plurality of decoding processing units, some of the decoding processing units have a unit code data U at the beginning. Thus, partial data that matches the boundary position is provided, and these decoding processing units can execute correct decoding processing.

  Here, the principle of decoding the encoded data string shown in FIG. 9C by parallel processing by eight decoding processing units will be specifically described with reference to FIGS. The data sequence shown in the upper part of FIG. 10 is obtained by dividing the encoded data sequence shown in FIG. 9C into 4-bit blocks B1 to B11. In addition, although a bit string “***” is shown in the block B11, this is for convenience because the bit string following the unit code data U5 is not clearly shown in FIG. 9 (c). Actually, a bit string (a bit string constituting the unit code data U6) is entered in the portion “***”.

  Here, the eight decoding processing units are referred to as units Q1 to Q8, respectively. Each of the decoding processing units accommodates 16-bit continuous bit data corresponding to the maximum bit length Umax of the unit code data U, and has a function of executing decoding processing sequentially from the top. However, partial data shifted by N bits (4 bits in this example) is given to the eight decoding processing units. In the figure, the eight decoding processing units Q1 to Q8 are drawn with a shift of 4 bits in order to clearly show that the given partial data is shifted by 4 bits.

  That is, the first decoding processing unit Q1 is provided with the bit string of the first to sixteenth bits (blocks B1 to B4), and the second decoding processing unit Q2 is provided with the bit string of the fifth to twentieth bits (block B2 to B5) are provided, and the third decoding processing unit Q3 is provided with the 9th to 24th bit strings (blocks B3 to B6), and so on.

  Now, assume that the eight decoding processing units Q1 to Q8 have started decoding processing in parallel. FIG. 11 shows the result of the decoding process in each unit. In the figure, a bold ellipse indicates a bit string that matches the identification code in the encoding table shown in FIG. 9B by the match determination process, and a circle indicated at the tip of the arrow pointing upward from the ellipse. The number indicates the bit length b corresponding to the matched identification code.

  For example, in the decoding process performed by the first decoding processing unit Q1, first, the presence or absence of a matching identification code C is checked for the bit “0” of the first bit. There is no matching identification code in the table of FIG. Then, next, the presence or absence of a matching identification code C is examined for the bit string “01” of the first and second bits, but there is no matching identification code. Further, when the presence or absence of a matching identification code C is examined for the bit string “011” of the first to third bits, the identification code corresponding to the bit length “5” is finally found as a matching code. An ellipse “011” and a circle number “5” above the line of the unit Q1 in the figure indicate that such a match recognition is performed. Since the bit length “5” is recognized, the subsequent 5-bit bit string “11100” is extracted as actual data, and the 8-bit data “00011100” is restored. [28] shown on the right side of the row of the unit Q1 in the figure is a decimal notation of the 8-bit data “00011100”.

  Subsequently, the first decoding processing unit Q1 checks the presence or absence of a matching identification code C for the bit “1” of the ninth bit, but there is no matching identification code. Then, next, the presence or absence of a matching identification code C is examined for the bit string “10” of the ninth to tenth bits, but there is no matching identification code. In this way, when the bit string to be matched is extended bit by bit, the identification code corresponding to the bit length “8” is finally found for the 9th to 16th bit strings “10111010”. . An ellipse “10111010” and a circle number “8” shown above in the row of the unit Q1 in the figure indicate that such matching recognition is performed. Here, since the bit length “8” has been recognized, an attempt is made to extract the subsequent 8-bit bit string as actual data. However, the first decoding processing unit Q1 receives the bit string after the block B5. The process ends in failure. [ERR] following [28] shown on the right side of the row of the unit Q1 in the figure indicates that the decoding process of the next actual data has failed.

  Eventually, the decoding process by the first decoding processing unit Q1 succeeds in decoding the first actual data [28], but fails in decoding the next actual data ([ERR]). Thus, if the decoding process fails, the process ends there. The description “P1 = 8” at the right end of the line of the unit Q1 in the drawing indicates that the normal processing bit length P1 is “8”. Here, the normal processing bit length refers to the length of a bit string involved in normal decoding processing. In the case of the above example, since the process was normally performed until the process of restoring the numerical value [28], the bit lengths up to the first to eighth bits involved in the restoration of the numerical value [28] are This is the normal processing bit length P1.

  Next, let's look at the decoding process performed by the second decoding processing unit Q2. The unit Q2 first checks the presence or absence of a matching identification code C for the first bit “1”. There is no matching identification code in the table of FIG. Then, next, the presence or absence of a matching identification code C is examined for the bit string “11” of the first and second bits, but there is no matching identification code. In this way, the bit string to be matched is extended bit by bit, but after all, no matching identification code is found. Therefore, normal decoding processing is not performed at all. The description of [ERR] and “P2 = 0” shown on the right side of the row of the unit Q2 in the figure indicates that normal decoding processing is not performed at all and the normal processing bit length P2 is “0”. Yes.

  Next, let's look at the decoding process performed by the third decoding processing unit Q3. When the unit Q3 repeats the process of finding a matching identification code while extending the bit string to be matched by one bit at a time, the bit string “10111010” of the first to eighth bits is finally set to the bit length “8”. A corresponding identification code is found as a matching code. The ellipse “10111010” and the circled number “8” shown above in the row of the unit Q3 in the figure indicate that such match recognition is performed. Here, since the bit length “8” is recognized, the subsequent 8-bit bit string “11111011” is extracted as actual data, and the 8-bit data “11111011” is restored. [251] shown on the right side of the row of the unit Q3 in the figure is a decimal notation of the 8-bit data “11111011”. At this time, since no unprocessed bits remain in the third decoding processing unit Q3, the decoding process ends here. In the description of [251] and “P3 = 16” shown on the right side of the row of the unit Q3 in the figure, the numerical data [251] is restored by normal processing, and the normal processing bit length P3 is “16”. It is shown that.

  The decoding process performed by the fourth decoding processing unit Q4 is as follows. When the unit Q4 repeats the process of finding a matching identification code while extending the bit string to be matched by one bit at a time, the bit length “10101” of the first to fifth bits corresponds to the bit length “7”. Is found as a matching code. An ellipse “10101” and a circle number “7” above it shown in the row of the unit Q4 in the figure indicate that such match recognition is performed. Here, since the bit length “7” is recognized, the subsequent 7-bit bit string “1111011” is extracted as actual data, and the 8-bit data “011111011” is restored. [123] shown on the right side of the row of the unit Q4 in the figure is a decimal notation of the 8-bit data “011111011”.

  The fourth decoding processing unit Q4 further continues the decoding process. Then, the bit string “010” of the 13th to 15th bits is found as a code that matches the identification code corresponding to the bit length “1”. An ellipse “010” and a circle number “1” above the line of the unit Q4 in the figure indicate that such a match recognition is performed. Here, since the bit length “1” is recognized, the 1-bit data “1” subsequent thereto is extracted as actual data, and the 8-bit data “00000001” is restored. [1] shown on the right of [123] on the right side of the row of the unit Q4 in the figure is a decimal notation of the 8-bit data “00000001”. At this point, since no unprocessed bits remain in the fourth decoding processing unit Q4, the decoding processing ends here. In the description “P4 = 16” shown at the right end of the row of the unit Q4 in the figure, the bit length P4 of the normal processing bits involved in the process of restoring the numerical data [123] and [1] is “16”. It is shown that.

  What should be noted in the decoding process by the fourth decoding processing unit Q4 is that all the normal decoding processes have been performed, and the numerical values [123] and [1] have been restored. Data [123] is numerical data that should not be restored. The encoded data sequence shown in the upper part of FIG. 11 is obtained by encoding the numerical data [28] [251] [1] [13] [3] shown in FIG. 1, and [28] [251] [1] ] Is originally numeric data to be restored, but [123] is not included in the numeric data string shown in FIG. Therefore, in the decoding process shown in FIG. 11, even numerical data obtained by normal processing is not necessarily numerical data to be decoded. However, numerical data such as [123] is not adopted in the final data organization stage, as will be described later, so that no problem occurs.

  In the subsequent decoding process performed by the fifth decoding processing unit Q5 and the sixth decoding processing unit Q6, no matching identification code is found and no normal decoding process is performed at all. In the description of [ERR] and “P5 = 0” and “P6 = 0” shown on the left side of the rows of the units Q5 and Q6 in the figure, normal decoding processing is not performed at all, and normal processing bit lengths P5 and P6 Is “0”.

  In the decryption processing performed by the next seventh decryption processing unit Q7, as shown in the figure, three numerical data [1] [13] [3] are extracted as actual data by normal processing. The normal processing bit length P7 at this time is “16”. Then, in the decoding process performed by the last eighth decoding processing unit Q8, as shown in the figure, two numerical data [13] [3] are extracted as actual data by normal processing. Thereafter, the decoding process is continued for the portion “***”, but here, the decoding process for the portion “***” has failed because a valid bit string is interrupted. Try. Therefore, as shown in the figure, the result [13] [3] [ERR] is obtained, and the normal processing bit length P8 at this time is “12”. Here, the numerical data [13] [3] are restored in duplicate in the units Q7 and Q8, but since only one of them is adopted in the final data organization stage, no problem occurs.

  After all, referring to FIG. 11, the unit Q1 is given partial data starting from the beginning of the unit code data U1, the unit Q3 is given partial data starting from the beginning of the unit code data U2, and the unit Q7 is given Is given partial data starting from the head of the unit code data U3, and the unit Q8 is given partial data starting from the head of the unit code data U4. Accordingly, these units Q1, Q3, Q7, and Q8 can perform normal decoding processing at least initially. On the other hand, since partial data starting from the middle of the unit code data is given to the units Q2, Q5, and Q6, normal decoding processing cannot be performed from the beginning, and the processing ends in failure.

  It should be noted that although the unit Q4 is given partial data starting from the middle of the unit code data, normal decoding processing has been completed. As described above, even when partial data starting from the middle of the unit code data is given, the normal decoding process may be completed by chance. However, as will be described later, in the event that a normal decoding process is accidentally performed in the final data organization stage, the processing result is not adopted, so no problem occurs.

  Now let's explain the final data organization process. The basic idea of the data organization stage processing is to first determine the first decoding processing unit Q1 as the first selection unit, recognize the final bit that has been normally decoded by this selection unit, and The process of continuing as much as possible the process of determining another unit to which the partial data with the bit immediately after the bit as the first bit was distributed as the new adopted unit was performed, and decoding was performed normally in each adopted unit The decrypted data string is generated by collecting numerical data.

  This will be described with reference to the specific example described above. FIG. 12 is obtained by adding normal processing end lines Z0 to Z3 to the diagram of the decoding processing process shown in FIG. The normal processing end lines Z0 to Z3 indicate end portions of the bit string on which normal decoding processing has been performed, and the positions thereof can be determined based on the normal processing bit lengths P1 to P8.

  First, the unit Q1 is determined as the first adopted unit, and the normal processing end line Z0 is drawn at the head position of the adopted unit Q1. Next, with reference to the normal processing bit length P1 = 8 for the selected unit Q1, the normal processing end line Z1 is drawn at the eighth bit (P1 bit) position from the normal processing end line Z0. Then, another unit Q3 having the normal processing end line Z1 as the head position is determined as a new selection unit, and the normal processing bit length P3 = 16 for the selection unit Q3 is referred to, and the normal processing end line Z1 A normal processing end line Z2 is drawn at the position of the 16th bit (P3th bit). Further, another unit Q7 having the normal processing end line Z2 as the head position is determined as a new selection unit, and the normal processing bit length P7 = 16 for the selection unit Q7 is referred to, and the normal processing end line Z2 A normal processing end line Z3 is drawn at the position of the 16th bit (P7th bit).

  In this way, the units Q1, Q3, and Q7 are the adopted units. FIG. 13 is a diagram showing the normal processing bit portions in the three adopted units Q1, Q3, and Q7 surrounded by a thick frame. Focusing on the portion of the normal processing bit surrounded by the thick frame, it becomes a section of normal processing end lines Z0 to Z1, a section of normal processing end lines Z1 to Z2, and a section of normal processing end lines Z2 to Z3, which are continuous with each other. It becomes a section. Therefore, if the numerical data obtained by the normal decoding process by these three adopted units Q1, Q3, and Q7 are collected, the numerical data string that should be restored can be obtained. That is, as shown in FIG. 13, if the numerical data restored by these adopted units Q1, Q3, and Q7 are collected and arranged, [28] [251] [1] [13] [3] are obtained. Matches the original numeric data string shown.

  In the example shown in FIG. 12, the numerical data [123] [1] is restored by the unit Q4 and the numerical data [13] [3] is restored by the unit Q8, but the units Q4 and Q8 are the selected units. Therefore, these numerical data are discarded without being used at all. Therefore, in this case, the units Q4 and Q8 have performed useless processing, but contributed to enjoy the merit of shortening the decoding time by parallel processing.

  In the end, in the decoding process described above, actually, all of the eight units Q1 to Q8 perform the decoding process in parallel. However, the unit code data for the encoded data string shown in the upper part of FIG. The portion U1 (in fact, including part of the subsequent unit code data U2) is given to the unit Q1, the portion of the unit code data U2 is given to the unit Q3, and the portions of the unit code data U3, U4, U5 are Q7 is the same as the decoding of the unit code data U1 to U5 by the parallel processing by these three decoding processing units.

  Thus, decoding of the unit code data U1 to U5 is completed by the first parallel processing of the eight units Q1 to Q8. That is, the first parallel processing completes the decoding of the blocks B1 to B10 in the encoded data string shown in the upper part of FIG. Therefore, in the second parallel processing, the same process as the first parallel processing may be repeated from the beginning of the undecoded portion of the encoded data string, that is, the beginning of the block B11. In this way, if the parallel processing is repeatedly executed, each block constituting the encoded data string can be sequentially decoded.

  In the above-described embodiment, an example in which the reference bit length N is set to 4 has been described. However, the reference bit length N may be an arbitrary integer as long as it is an integer of 2 or more. Each of the decoding processing units Q1 to Q8 has a function of accommodating 16-bit continuous bit data corresponding to the maximum bit length Umax of the unit code data U and executing a decoding process. A decoding processing unit having a function of performing decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax) may be used. Therefore, for example, when the maximum bit length Umax = 16 bits, a unit having a function of setting L = 20 bits, accommodating 20-bit continuous bit data, and executing a decoding process may be used.

  Furthermore, in the above-described embodiment, an example of parallel processing using eight decoding processing units Q1 to Q8 has been shown. However, the number M of decoding processing units to be used is not necessarily set to M = 8. , Even if a prime number such as M = 7 is set, there is no problem. However, it is preferable to use a plurality of M decoding processing units such that M ≧ 1 + L / N in order to ensure that the decoding time reduction effect by parallel processing is obtained. If it does so, since the normal decoding process of two or more unit code data can always be performed in one parallel processing, the effect of parallel processing will certainly be acquired each time.

<<< §5. Basic procedure of encoding method according to the present invention >>
Next, the basic procedure of the encoding method according to the present invention will be described with reference to a flowchart. FIG. 14 is a flowchart showing the basic procedure of the numerical data string encoding method according to the present invention. Each step constituting this procedure is actually executed by an arithmetic processing unit such as a computer or an integrated circuit.

  First, in the data input stage of step S11, a process of inputting a numerical data string to be encoded to the arithmetic processing unit is performed. The numeric data string input in step S11 is, for example, a data string represented by fixed-length bits as shown in FIG. 2, and the purpose of the encoding process performed here is numeric data consisting of these fixed-length bits. The sequence is to encode the sequence using a variable-length bit sequence.

  On the other hand, in the table input stage of step S12, processing for inputting an encoding table indicating a unique identification code corresponding to each bit length to the arithmetic processing unit is performed. As shown in FIG. 9B, the encoding table input in step S12 has a plurality of bit lengths b (0 to 8 in the illustrated example) within a predetermined range sufficient to represent actual data. ) Is a variable-length coding table showing the correspondence between individual bit lengths b and unique identification codes C corresponding to the bit lengths b, and satisfies the following two conditions.

  The first condition is a condition necessary to make the variable-length identification code C recognizable. “When focusing on any identification code in this table, the bit length of the target identification code itself is set. The condition is that there is no other identification code in the table in which the a-bit portion from the beginning is the same as the target identification code when a is set. If an identification code group satisfying such a condition is used, as described in §1, it is possible to perform a match determination process in which one bit is compared from the head when decoding is performed.

  The second condition is a condition peculiar to the present invention. “When any identification code in this table is focused, when the bit length corresponding to the targeted identification code is b, a predetermined criterion is set. The condition is “a + b = k × N” (where k is an arbitrary integer) for a bit length N (where N is an integer of 2 or more). The fact that using the identification code group that satisfies the second condition enables parallel processing using a plurality of decoding processing units when performing decoding has already been described in Section 4 with examples. It is as follows.

  Thus, when the numerical data string to be encoded and the encoding table used for encoding are prepared, actual encoding processing is executed in steps S13 to S17.

  First, in the data extraction stage of step S13, a process of sequentially extracting individual numerical data from the input numerical data string is performed. For example, in the example shown in FIG. 2, numerical data D1, D2, D3,... Consisting of fixed-length bits are extracted one by one in order. In other words, an 8-bit fixed-length bit string D1 “00011100” indicating the numerical value “28” is extracted first.

  In the next actual data generation step S14, processing for generating actual data is performed by deleting redundant bits from the extracted numerical data. In the case of the above example, the process of deleting the leading zero of the fixed-length bit string D1 “00011100” is performed, and actual data “11100” is generated. The actual data created for the 8-bit fixed-length bit strings D1, D2, D3,... Shown in FIG. 2 is a variable-length bit string as shown in FIG. In any case, a process of deleting leading zeros from the bit string constituting each numerical data is performed. Looking at the variable-length bit strings shown in FIG. 3, it can be seen that the first bit is 1 and unnecessary 0 is deleted.

  In general, there are two methods for handling numeric data indicating 0 (8-bit fixed-length bit string “00000000”). The first method is a method of expressing the numerical value 0 by a variable length bit “0”. In this case, 1-bit actual data having variable length bits “0” is generated for numerical data having a fixed length bit string “00000000”. Thus, since 1-bit actual data is generated even for the numerical value 0, the minimum value of the bit length b is “1” as the variable-length coding table, as in the example shown in FIG. Is sufficient. As will be described later, in the present invention, it is also possible to handle negative values, and when expressing negative values using “1's complement”, it is necessary to use the second method described below. is there.

  The second method is a method of expressing the numerical value 0 by a virtual bit having a length of 0 bits. In this case, actual data having a variable length bit “” having a length of 0 bits is generated for numerical data having a fixed length bit string “00000000”. That is, the actual data in this case does not have substantial bits, and actually, no bits are arranged in the actual data portion. In this case, the actual data is a virtual bit string having a bit length of 0, and the unit code data U is substantially composed only of the bit string that constitutes the identification code C. In this way, actual data having a length of 0 bits is created for the numerical value 0. Therefore, as the variable length coding table, the minimum value of the bit length b is “as shown in FIG. 9B. It is necessary to use a table that is “0”.

  From the viewpoint of reducing the data capacity as much as possible, the second method described above is preferable. In addition, the embodiments described so far are embodiments on the premise that the numerical data to be encoded is data indicating a positive value, but in practice it indicates a negative value. It is also possible to handle data. In a binary representation format using a general fixed-length bit string, the value “0” is expressed by arranging bit 0 like “00000000”, and the positive value “2” is 0 at the head of the actual data like “00000010”. The negative value “−2” is expressed by padding 1 at the beginning of the actual data as “11111101” (in the case of 1's complement).

  Therefore, when handling signed numeric data in which positive and negative numeric values are mixed, all bits are redundant bits for the value “0”, and the bit “0” that is consecutively added to the positive value is assigned to the positive value. Redundant bits are used, and for negative values, real data can be generated by setting bit “1” consecutively added to the head as redundant bits and deleting these redundant bits. That is, in step S14, as actual data indicating the extracted numerical data, when the numerical data is data indicating 0, a virtual bit string having a bit length of 0 is used as data indicating a positive value. May generate a variable-length bit string that does not include 0 at the beginning, and a variable-length bit string that does not include 1 at the beginning if the data indicates a negative value.

  In the identification code selection stage in step S15, a process for selecting the identification code C corresponding to the bit length b of the actual data generated in step S14 is performed with reference to the encoding table input in step S12. For example, in the example shown in FIG. 9A, the identification code C1 corresponding to the bit length b (indicated by the circled number “5” in the figure) of the actual data D1 “11100” created in step S14. “011” is selected from the encoding table shown in FIG.

  Then, in the unit code data generation stage of step S16, unit code data indicating the extracted numerical data is generated by adding the identification code selected in step S15 to the head of the actual data generated in step S14. The In the above example, the identification code C1 “011” is added to the head of the actual data D1 “11100”, and the unit code data U1 “01111100” is generated as shown in FIG. 9C.

  In the subsequent step S17, a repetitive process for returning to the process from step S13 is executed until the process for all data is completed. That is, the above-described data extraction step S13, actual data generation step S14, identification code selection step S15, and unit code data generation step S16 are repeatedly executed for each of the numerical data constituting the input numerical data string. As a result, unit code data U1, U2, U3, U4, U5,... As shown in FIG.

  In the final step S18, a data output stage is performed in which the generated unit code data are arranged in order and output as an encoded data string. As a result, a data string in which unit code data U1, U2, U3, U4, U5,... Are arranged as shown in FIG. 9C is output as an encoded data string.

  In the data output stage of step S18, it is preferable to output a data file including the encoded data string and the encoding table used for the encoding process. FIG. 15 is a block diagram showing an example of the structure of the encoded data file F created at this data output stage. A general data file such as image data includes a header part F1, a main body part F2, and a footer part F3 as shown in the figure. Here, the original data to be accommodated in the encoded data file F, that is, unit code data U1, U2, U3, U4, U5,... As shown in FIG. An encoded data string configured side by side is incorporated.

  On the other hand, auxiliary information indicating the format, format, capacity, etc. of data incorporated in the main body F2 is usually incorporated in the header part F1. In the embodiment shown in FIG. 15, the encoding part T used for the encoding process is incorporated in the header part F1. By doing so, it is possible to use the encoding table T incorporated in the header part F1 as it is when performing decoding to be described later. Of course, the encoding table T may be incorporated in the footer part F3. In FIG. 15, each of the unit code data U1, U2,... Is shown as a block having the same width, but actually, the data lengths thereof are different (however, both are predetermined). The reference bit length N (where N is an integer multiple of 2 or more)).

  After all, the encoded data file F shown in FIG. 15 is data in which actual data D consisting of a bit string having the bit length b is arranged following the identification code C indicating the predetermined bit length b, and the total length is predetermined. Are arranged by arranging a plurality of unit code data U (maximum bit length Umax) having different lengths set to be an integral multiple of a reference bit length N (where N is an integer of 2 or more). The data file includes a bit sequence data to be processed and a coding table T indicating a specific bit length b corresponding to each identification code C. The data file F is a computer-readable information recording medium. Can be recorded and distributed.

  The encoding table T included in the data file F is a table used for an encoding method for encoding a numeric data string using a variable-length bit string, and has a plurality of bit lengths within a predetermined range. The correspondence relationship between individual bit lengths and unique identification codes corresponding to the bit lengths is shown. When any one of the identification codes in the table is focused, When the bit length is a, there is no other identification code in the table in which the portion of a bits from the beginning is the same as the target identification code, and the bit length corresponding to the target identification code Is a table that satisfies the condition of “a + b = k × N” (where k is an arbitrary integer) for a predetermined reference bit length N (where N is an integer of 2 or more). To become.

  FIG. 16 is a block diagram showing another example of the structure of the encoded data file F. In the data output stage of step S18, as in the example shown in FIG. 16, a data file F including an encoded data string and table specifying information for specifying an encoding table used for encoding processing is output. You may do it.

  The difference between the file F shown in FIG. 15 and the file F shown in FIG. 16 is that the latter specifies a coding table used for coding processing instead of incorporating the coding table T itself into the header part F1. The specific information H is incorporated. The table specifying information H is not the encoding table itself, but is information such as a file name and URL for specifying the encoding table. When performing the decoding, the table specifying information H is used to This is information for making it possible to obtain an encoding table necessary for decoding.

  For example, in the example shown in the figure, four types of encoding tables T1 to T4 are prepared as separate files, and information for specifying any of these tables is incorporated into the header part F1 as table specification information H. It will be. Specifically, for example, if the table T3 is a table used for encoding, information such as the file name of the table T3 and the URL indicating the acquisition location of the table T3 is used as the table specifying information H as a header. It is incorporated in the part F1. When decoding is performed, a necessary encoding table can be obtained using this table specifying information H.

  After all, the encoded data file F shown in FIG. 16 is data in which real data D consisting of a bit string having the bit length b is arranged after the identification code C indicating the predetermined bit length, and the total length is predetermined. It is configured by arranging a plurality of unit code data U (maximum bit length Umax) having different lengths set to be an integral multiple of the reference bit length N (where N is an integer of 2 or more). And a table specifying information H for specifying a coding table T indicating a specific bit length b corresponding to each identification code C. The data file is read by a computer. It can be recorded and distributed on possible information recording media.

  As described in §3, as the coding table input in step S12 is practically shorter as the frequency of appearance of the bit length b of the actual data is higher as in the example shown in FIG. It is preferable to use a Huffman coding table associated with an identification code having a bit length a. Such a Huffman coding table replaces two identification codes such that the difference in the corresponding bit length b is an integer multiple of N in the coding table shown in FIG. It can be created by performing work.

  For this purpose, after the data input stage of step S11, a frequency counting stage for counting the appearance frequency of the bit length b of the actual data is performed on the input numerical data string, and the input is performed after the table input stage of step S12. In the existing standard coding table, the bit length b having a difference that is an integral multiple of the reference bit length N is subjected to a process of exchanging the contents of the table, so that the appearance frequency of the bit length b of the actual data increases. Then, a table correction stage for generating a corrected encoding table associated with an identification code having a shorter bit length a is performed, and the corrected encoding table is referred to in the identification code selection stage of step S15. Thus, the identification code may be selected.

<<< §6. Basic procedure of decoding method according to the present invention >>
Next, the basic procedure of the decoding method according to the present invention will be described with reference to a flowchart. FIG. 17 is a flowchart showing the basic procedure of the numerical data string decoding method according to the present invention. Each step constituting this procedure is actually executed by an arithmetic processing unit such as a computer or an integrated circuit.

  The decoding method described here is the encoded data string encoded by the encoding method described in §5, that is, “the identification code C indicating the predetermined bit length b is followed by the bit length b. Unit code data U (maximum bit length) that is real data D consisting of a bit string, and whose total length is an integer multiple of a predetermined reference bit length N (where N is an integer of 2 or more) Umax) ”is an object of decoding processing, and an object is to restore numerical data corresponding to individual actual data.

  The basic principle of this decoding method is that, as already described in §4, the encoded data string is divided into integer multiples of N bits to generate a plurality of partial data, and each partial data is decoded into a plurality of M units. Distribute to the processing units, perform decoding processing on the distributed partial data by parallel processing of the plurality of M decoding processing units, and generate a decoded data string by arranging numerical data that has been normally decoded Is to do.

  First, in the data input stage of step S21, a process of inputting an encoded data string to be decoded into an arithmetic processing device including a plurality of M decoding processing units is performed. Specifically, for example, an encoded data string expressed by variable length bits as shown in FIG. 9C is input.

  On the other hand, in the table input stage of step S22, processing for inputting an encoding table indicating a specific bit length corresponding to each identification code to the arithmetic processing unit is performed. Of course, the encoding table input here needs to be substantially the same as the table used in the encoding processing stage for generating the encoded data string input in step S21. Therefore, practically, as shown in FIG. 15, the encoded data file F in which the encoding table T used for the encoding process is incorporated or the code used for the encoding process as shown in FIG. The encoded data string is stored using the encoded data file F in which the table specifying information H for specifying the encoding table T is incorporated, and when the decoding is performed, the encoded data file F It is preferable to be able to hand over the information of the encoding table used for the decoding together with the encoded data string.

  For example, as shown in FIG. 15, when a data file F including an encoded data string and an encoding table T used for the encoding process is given, in the data input step S21, from the data file F The process of extracting the encoded data string is performed, and the process of extracting the encoding table T from the data file F may be performed in the table input step S22. Further, as shown in FIG. 16, when a data file including an encoded data string and table specifying information H for specifying an encoding table used for encoding processing is given, in the data input stage S21, A process of extracting the encoded data string from the data file F is performed, and after the process of extracting the table specifying information H from the data file F in the table input step S22, a table specified by the table specifying information H is obtained. Select and use.

  In the subsequent data distribution stage of step S23, a plurality of M decoding processing units each having a function of performing decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax). Then, a process of distributing a part of the encoded data string input in step S21 as partial data is performed. The embodiment shown in FIG. 10 is an example in which N = 4, L = 16, Umax = 16, and M = 8, and each of the eight decoding units having a function of performing decoding processing on 16-bit continuous bit data. For the processing units Q1 to Q8, processing for distributing a part of the encoded data string input in step S21 as partial data is performed.

  When this distribution stage process is described in general terms, the (N × (i−1) +1) -th bit to (N × (i−1) + L) counting from the beginning of the undecoded portion of the encoded data string. ) This is a process of distributing the bit string up to the bit to the i-th unit (i = 1 to M). In the case of the embodiment shown in FIG. 10, since N = 4, L = 16, and M = 8, the (4 × (i−1) +1) th counted from the head of the undecoded portion of the encoded data string. This is a process of distributing the bit string from the bit number to the (4 × (i−1) +16) th bit to the i-th unit (i = 1 to 8). For example, the bit string distributed to the first decoding processing unit Q1 is a bit string from the first bit to the 16th bit, counting from the beginning of the undecoded portion of the encoded data sequence, with i = 1. The bit string distributed to the second decoding processing unit Q2 is a bit string from the fifth bit to the twentieth bit, counting from the beginning of the undecoded portion of the encoded data sequence, with i = 2.

  The decoding process stage of the next step S24 is a stage performed as parallel processing by M decoding process units. That is, by parallel processing by M decoding processing units, decoding processing for extracting numerical data corresponding to actual data from each distributed partial data is performed while referring to the encoding table input in step S22. As already described in §4, this decoding process is not always performed normally. For example, in the unit described as [ERR] in FIG. 11, normal decoding processing is not performed. Therefore, in this decoding processing stage, the processing is continued as much as possible from the beginning of the distributed partial data as long as normal decoding processing is possible, and if normal decoding processing cannot be performed, the processing is interrupted there ( Alternatively, as described in §14, the processing may be interrupted at a predetermined time.)

  In the subsequent data organization stage of step S25, a process of generating a decoded data sequence in which numerical data corresponding to individual actual data are arranged by selecting the results of the decoding process by the M decoding processing units is performed. . Specifically, when processing results are obtained from M decoding processing units by one parallel processing, the first unit is first determined as the first adopted unit, and normal decoding processing is performed by this adopted unit. The process of recognizing the last bit performed and determining as another newly adopted unit another unit to which the partial data having the bit immediately after the last bit as the first bit is distributed is performed as much as possible. A process of collecting and arranging the numerical data successfully decrypted by the adopted unit is performed.

  For example, in the embodiment shown in FIG. 12, the first unit Q1 is first determined as the first adopted unit, and the final bit subjected to normal decoding processing by this adopted unit Q1 is determined by the normal processing bit length P1. Recognized as the eighth bit (the left bit of the normal processing end line Z1). Then, a process of determining another unit Q3 to which a partial data having a bit immediately after the last bit (the right bit of the normal processing end line Z1) as a first bit is distributed as a new adopted unit is performed. Further, the final bit that has been normally decoded by the new adoption unit Q3 is recognized as the 24th bit by the normal processing bit length P3 (the left bit of the normal processing end line Z2). Then, a process of determining another unit Q7 to which a partial data having a bit immediately after the last bit (the right bit of the normal processing end line Z2) as a first bit is distributed as a new adopted unit is performed. Further, the final bit that has been normally decoded by the new adoption unit Q7 is recognized as the 40th bit by the normal processing bit length P7 (the left bit of the normal processing end line Z3). Then, the numerical data [28] [251] [1] [13] [3] successfully decoded in each of the adopted units Q1, Q3, Q7 is collected and arranged.

  In the subsequent step S26, an iterative process returning to the process from step S23 is executed until the process for all the data is completed, that is, until the decoding of all the parts of the input encoded data string is completed. In the data distribution step S23, the above-described distribution process is repeatedly executed from the beginning of the undecoded portion of the encoded data sequence (in the example shown in FIG. 13, from the block B11). In step S24, each time new partial data is distributed, parallel decoding processing by each decoding processing unit is executed, and in step S25, the numerical data thus collected by the plurality of parallel processings are obtained. By arranging them, a decoded data string is generated.

  Finally, in the data output stage of step S27, the generated decoded data string is output.

  As described above, in order to ensure that the effect of parallel processing is obtained every time, it is possible to perform normal decoding processing of two or more unit code data in one parallel processing. do it. For this purpose, partial data is distributed to a plurality of M decoding processing units such that M ≧ 1 + L / N in the data distribution stage in step S23, and these M decoding processes are performed in the decoding processing stage in step S24. What is necessary is just to perform parallel processing by a unit.

<<< §7. Basic configuration of encoding apparatus according to the present invention >>
Next, the basic configuration of the encoding apparatus according to the present invention will be described with reference to the block diagram shown in FIG. The apparatus shown here can actually be constituted by an arithmetic processing unit such as a computer or an integrated circuit.

  As shown in FIG. 18, the encoding apparatus includes a data storage unit 110, a table storage unit 120, a data extraction unit 130, an actual data generation unit 140, an identification code selection unit 150, a unit code data generation unit 160, and a data output unit 170. The numeric data sequence E composed of fixed-length bits is encoded by referring to the encoding table T, and the encoded data sequence S composed of variable-length bit sequences is generated.

  The data storage unit 110 is a component that inputs and stores a numeric data string E to be encoded. For example, a numeric data string E composed of a fixed-length bit string as illustrated in FIG. 2 is stored. On the other hand, the table storage unit 120 is a component that stores a coding table T indicating a unique identification code C corresponding to each bit length b. For example, a variable length code as illustrated in FIG. Stores the conversion table.

  Here, as described above, the encoding table stored in the table storage unit 120 includes individual bit lengths b for a plurality of bit lengths b within a predetermined range sufficient to represent the actual data D. , Is a table showing the correspondence relationship with the unique identification code C corresponding to the bit length b. “Condition 1: When any identification code in this table is focused, the bit of the focused identification code itself When the length is a, there is no other identification code in this table in which the a-bit portion from the beginning is the same as the target identification code. ”And“ Condition 2: corresponding to the target identification code ” “B + k = N” (where k is an arbitrary integer) with respect to a predetermined reference bit length N (where N is an integer equal to or greater than 2) when the bit length is b ” Satisfy the conditions It is a table.

  The data extraction unit 130 is a component that sequentially extracts individual numerical data D1, D2, D3,... From the numerical data string E stored in the data storage unit 110. For example, if the input numerical data D1, D2, D3,... Is an 8-bit fixed-length bit string as shown in FIG. Process to extract as data.

  The actual data generation unit 140 is a component that generates actual data by deleting redundant bits from the extracted numerical data. Specifically, in the case of handling signed numeric data, a virtual bit string having a bit length of 0 is used as actual data indicating the extracted numeric data when the numeric data is data indicating 0. If the data is a positive value, a variable-length bit string that does not include a leading zero is generated (the leading bit 0 is deleted until bit 1 appears), indicating a negative value. In the case of data, a variable-length bit string not including 1 at the beginning may be generated (bit 1 at the beginning is deleted until bit 0 appears).

  The identification code selection unit 150 refers to the encoding table T stored in the table storage unit 120 and selects an identification code C corresponding to the bit length b of the actual data generated by the actual data generation unit 140. The unit code data generation unit 160 adds the identification code selected by the identification code selection unit 150 to the head of the actual data generated by the actual data generation unit 140, so that the data extraction unit 130 extracts it. This is a component for generating unit code data indicating the numerical data.

  The data output unit 170 is a component that arranges the unit code data U generated by the unit code data generation unit 160 in order and outputs it as an encoded data string S. Specifically, an encoded data string as shown in FIG. 9 (c) is output. In the case of the embodiment shown here, the data output unit 170, together with the encoded data string S, stores the encoding table T stored in the table storage unit 120 or the table specifying information H that specifies the encoding table T. It has a function to output. For example, the data file F output from the data output unit 170 is a data file having the structure shown in FIG.

<<< §8. Basic configuration of decoding apparatus according to the present invention >>
Next, the basic configuration of the decoding apparatus according to the present invention will be described with reference to the block diagram shown in FIG. The apparatus shown here can actually be constituted by an arithmetic processing unit such as a computer or an integrated circuit.

  The decoding apparatus described here is the encoded data string S encoded by the encoding apparatus described in §7, that is, “the identification code C indicating the predetermined bit length b is followed by the bit length b. The unit code data U (maximum bit) that is set to be an integral multiple of a predetermined reference bit length N (where N is an integer equal to or greater than 2). The encoded data string formed by arranging a plurality of sets of “long Umax)” is to be subjected to decoding processing, and processing for restoring numerical data corresponding to individual actual data is performed.

  As shown in FIG. 19, this decryption apparatus includes a data storage unit 210, a table storage unit 220, a data distribution unit 230, a plurality of M decryption processing units 240 (1) to 240 (M), a data organization unit 250, data The encoded data sequence S composed of the variable-length bit sequence is decoded by referring to the encoding table T, and the decoded data sequence G (original numerical data sequence E) composed of fixed-length bits is configured by the output unit 260. It has a function to generate.

  The data storage unit 210 is a component that receives and stores an encoded data sequence S to be decoded. For example, the data storage unit 210 includes an encoded data sequence S composed of a variable-length bit sequence as illustrated in FIG. Is stored. On the other hand, the table storage unit 220 is a component that stores a coding table T indicating a specific bit length b corresponding to each identification code C. For example, a variable length code as illustrated in FIG. Stores the conversion table. The encoding table stored in the table storage unit 220 has substantially the same contents as the encoding table stored in the table storage unit 120 shown in FIG. 18 when the encoded data string S is created. It is.

  Practically, as shown in FIG. 15, the encoded data file F in which the encoding table T used for the encoding process is incorporated or the encoding table used for the encoding process as shown in FIG. The encoded data file F is stored using the encoded data file F in which the table specifying information H for specifying T is incorporated, and the encoded data file F is encoded from the encoded data file F when decoding is performed. It is preferable to read out the information of the coding table used for decoding together with the data string S.

  For example, as shown in FIG. 15, when a data file F including an encoded data string and an encoding table T used for encoding processing is given, the data storage unit 210 reads the data file F from the data file F. A process of extracting and storing the encoded data string S may be performed, and the table storage unit 220 may perform a process of extracting and storing the encoded table T from the data file F. As shown in FIG. 16, when a data file F including an encoded data string and table specifying information H for specifying an encoding table used for encoding processing is given, the data storage unit 210 Then, the process of extracting and storing the encoded data string S from the data file F is performed, and after the table storage unit 220 performs the process of extracting the table specifying information H from the data file F, the table specifying information H It is sufficient to perform processing for reading and storing the table specified by the external.

  The data distribution unit 230 distributes a part of the encoded data sequence S stored in the data storage unit 210 as partial data to the M decoding processing units 240 (1) to 240 (M). It is. Specifically, as described in §6, the (N × (i−1) +1) th bit to the (N × (i−1) th bit counting from the beginning of the undecoded portion of the encoded data sequence S. The process of distributing the bit string up to the (+ L) th bit to the i-th unit (i = 1 to M) is repeatedly executed until the decoding of all parts of the encoded data string S is completed.

  In the embodiment shown here, the M decoding processing units 240 (1) to 240 (M) are exactly the same constituent elements, each having L bits (where L is an integer multiple of N, and L ≧ Umax) has a function of performing decoding processing on continuous bit data. Specifically, these M decoding processing units 240 (1) to 240 (M) can perform real operations from the distributed partial data with reference to the encoding table T stored in the table storage unit 220. It has a function of performing a decoding process for extracting numerical data corresponding to the data, and each time a new partial data is distributed from the data distribution unit 230, a normal decoding process can be performed in order from the top of the distributed partial data. Continue as long as possible. As described above, when normal decoding processing cannot be performed, the processing is interrupted there.

  The decoding processing by these M decoding processing units 240 (1) to 240 (M) is performed in parallel as parallel processing, and as a result, the effect of shortening the decoding processing time is obtained. become. However, as described above, in order to ensure that the effect of parallel processing is obtained every time, it is possible to always perform normal decoding processing of two or more unit code data in one parallel processing. It is preferable to do this. For that purpose, a plurality of M decoding processing units may be provided such that M ≧ 1 + L / N.

  In the case of the embodiment shown here, each decoding processing unit 240 sends to the data organization unit 250 the numerical data D restored by normal decoding processing and the normal indicating the number of bits involved in the normal decoding processing. If the processing bit length P and normal decoding cannot be continued, an error signal ERR indicating that fact is reported.

  For example, in the embodiment shown in FIG. 12, from the unit Q1, the numerical data “28” restored by the normal decoding process and the normal processing bit length “P1 =“ indicating the number of bits involved in the normal decoding process. 8 ”and the error signal“ ERR ”are reported, and the normal processing bit length“ P2 = 0 ”and the error signal“ ERR ”are reported from the unit Q2, and the unit Q3 From this, the restored numerical data “251” and the normal processing bit length “P3 = 16” are reported. Similar reports are made from the units Q4 to Q8.

  The data organization unit 250 selects a result of the decryption processing by the M decryption processing units 240 (1) to 240 (M), and generates a decrypted data string in which numerical data corresponding to individual actual data is arranged. It is a component to do. Specifically, when the data organization unit 250 obtains processing results from the M decoding processing units 240 (1) to 240 (M) by one parallel processing, first, the data organization unit 250 (1) ) As the first adopted unit, recognizes the last bit that has been successfully decoded by this adopted unit, and selects another unit to which partial data having the bit immediately after the last bit as the first bit is distributed. The process of deciding as a new adopted unit is continued as much as possible, the numerical data successfully decoded in each adopted unit is collected, and the numerical values collected respectively by one or more parallel processes A decoded data string is generated by arranging the data.

  In addition, the data organization unit 250 performs decoding on the data distribution unit 230 every time processing results from the M decoding processing units 240 (1) to 240 (M) are obtained by one parallel processing. A signal indicating the part is given. For example, in the embodiment shown in FIG. 13, since the decoding of the bit strings from blocks B1 to B10 has been completed, the data organization unit 250 has already decoded the block B10 up to the block B10. A signal indicating that it is a conversion unit is given. Specifically, for example, a signal indicating the position of the last bit of the block B10 (the 40th bit from the beginning) may be given. As a result, the data organization unit 250 recognizes that the head of the undecoded part that is the starting point for distribution for the next parallel processing is the 41st bit from the head (the head bit of the block B11). The distribution process can be performed from this starting point.

  The processing described above by the data organization unit 250 can be performed based on the numerical data D and the normal processing bit length P reported from the M decoding processing units 240 (1) to 240 (M). That is, the adopted unit among the M decoding processing units can be determined based on the normal processing bit length P. Specifically, first, the first unit 240 (1) is set as the first adopted unit. Subsequently, based on the normal processing bit length P reported from the first unit 240 (1), the final bit that has been normally decoded by the selected unit can be recognized. Another unit to which partial data having a bit immediately after the first bit is distributed can be specified as a new adopted unit. In the same manner, the adopted units can be sequentially determined, and finally, the decoded data string can be generated by arranging the numerical data D reported from each adopted unit in order. Further, by summing up the normal processing bit lengths P reported from the selected units, the already-decoded part can be recognized, and this can be reported to the data distribution part 230.

  In the embodiment shown here, each decoding processing unit 240 causes the data organization unit 250 to report an error signal ERR indicating that normal decoding processing could not be continued. As described above, the error signal ERR is not directly used in executing the processing in the data organization unit 250. Therefore, the report of the error signal ERR is not necessarily required and may be omitted. In practice, a report that the normal processing bit length P = 0 can be substituted for the error signal ERR.

  In this way, the data organization unit 250 can create the decoded data string G by one or more parallel processes. The data output unit 260 functions to output the decrypted data string G created in this way. This decoded data string G is the same as the original numerical data string E shown at the upper left of FIG.

<<< §9. Basic principle using 2D coding table >>
Each of the encoding tables used in the embodiments described so far shows a one-to-one correspondence between the bit length b of the actual data and the identification code C. Each identification code C is a specific bit. It was a code indicating information of length b. On the other hand, the embodiment described in §9 performs an operation in which the identification code C is provided with not only information of the bit length b but also additional information. Specifically, zero run length value R information is provided.

  First, the basic concept of adopting a zero run length value R will be briefly described. Consider a case where a numeric data string (decimal notation) as shown in FIG. 20 is encoded. Here, when the numerical data sequence shown in FIG. 20 is given as an 8-bit fixed-length bit sequence, the encoding method according to the present invention described so far is used by using the encoding table shown in FIG. 9 (b). Consider the case of converting to a variable-length bit string.

  FIG. 21 is a diagram illustrating a process for implementing such an encoding method. In the upper table of the figure, for each numerical data D (decimal notation), actual data D obtained by deleting redundant bits, an identification code C corresponding to the bit length b of the actual data D, The bit length of the unit code data U obtained by adding the identification code C to the head of the actual data D is shown. For example, the row of data number 1 corresponds to the actual data “11100” and the bit length “5” of this actual data for numeric data “28” (binary notation with 8-bit fixed length is “00011100”) ” The identification code “011” (refer to the table in FIG. 9B) and the bit length “8” of the unit code data “01111100” obtained by concatenating the identification code and the actual data are shown.

  A feature of the numerical data string shown in FIG. 20 is that a series of zeros is included in the middle. In general, image data often includes such consecutive zeros. In particular, image data in the JPEG format, which will be described later, usually includes a large number of consecutive zeros. The encoding process shown in FIG. 21 is based on the encoding method according to the basic embodiment described so far, and unit code data U is created for each of such consecutive zeros. . That is, the rows of data numbers 4 to 9 in the upper table of FIG.

  In the encoding table shown in FIG. 9B, when the numerical data is data indicating 0, a virtual bit string having a bit length of 0 is used as real data, and an identification code “1000” is assigned. Therefore, in the rows of data numbers 4 to 9 in the upper table of FIG. 21, there is no actual data and only the identification code “1000” is assigned. A part of the encoded data string created based on this table is shown in the lower part of FIG. The unit code data U1, U2, U3, U4, U5, U6 shown in the figure correspond to the original numerical data 28, 251, 1, 0, 0, 0, respectively. Since the unit code data U4, U5, U6 is data indicating the numerical value 0, there are no bits constituting the actual data, and it is configured only by the identification code “1000”.

  Looking at the U bit length column in the upper table of FIG. 21, it is either 4, 8, or 16, which is an integral multiple of the reference bit length N = 4. This is because encoding is performed using the encoding table shown in FIG. Therefore, the bit length of the unit code data U1, U2, U3, U4, U5, U6 shown in the lower part of FIG. As described above.

  In the encoding process shown in FIG. 21, 4-bit unit code data U of “1000” is created to represent the numerical value 0 as shown in the lower part of FIG. When consecutive 0s are included in a data string, it cannot be said that efficient encoding is necessarily performed. Therefore, for image data and the like that may contain many consecutive zeros, a technique is adopted in which the consecutive zeros are grasped as a run length of zero and represented by a run length value R. For example, in the example shown in FIG. 21, the data numbers 4 to 9 are expressed by a zero run length value R = 6, and the information of the run length value R = 6 is represented by a unit code for the data number 10. Use a method to include in the data.

  In the example shown in FIG. 21, the identification code “1001” corresponding to the bit length “4” of the actual data “1101” at the beginning of the numerical value “13” of the data number 10 (in FIG. 9B) By adding a table reference), a unit code code U10 of “10011101” is created. In this case, the identification code “1001” has only a function indicating the bit length “4” of the actual data. The unit code data U4 to U9 for the portions ˜9 can be omitted, and the data amount can be greatly reduced.

  For this purpose, an encoding table as shown in the lower part of FIG. 22 may be used. This encoding table is a table indicating a unique identification code corresponding to a combination of each bit length b and each run length value R, and is referred to as a two-dimensional encoding table here. For comparison, the encoding table used in the above embodiments (a table indicating a specific identification code corresponding to each bit length b) is referred to as a one-dimensional encoding table.

  This two-dimensional encoding table has a bit length b = 0 to 8 in the horizontal direction and a run length value R = 0 to 8 in the vertical direction. A predetermined identification code is assigned to any combination of the two. Is defined. For example, an identification code “C64” is defined for a combination of “bit length b = 4” and “run length value R = 6”. However, the illustrated identification codes C00 to C88 are not actual identification codes, but are replaced with simple abbreviations for convenience of explanation. Actually, each identification code is composed of a digital bit string in the same manner as the identification code defined in the conventional one-dimensional encoding table.

  In addition, for the two-dimensional encoding table, as in the one-dimensional encoding table described so far, “Condition 1: When any identification code in this table is focused, the bit of the target identification code itself When the length is a, there is no other identification code in this table in which the a-bit portion from the beginning is the same as the target identification code. ”And“ Condition 2: corresponding to the target identification code ” “B + k = N” (where k is an arbitrary integer) with respect to a predetermined reference bit length N (where N is an integer equal to or greater than 2) when the bit length is b ” It is necessary to satisfy the conditions.

  Furthermore, in the case of the illustrated example, a total of 99 identification codes are required to make a table covering the range of bit length b = 0 to 8 and run length value R = 0 to 8 (in practice, As will be described later, the identification codes C10, C20, C30,..., C70 do not need to be defined), and the above two conditions must be satisfied for all of these identification codes. Therefore, in practice, each identification code C00 to C88 is a code having a considerably long bit length (an example is shown in §11). However, for convenience of explanation, these identification codes are indicated using abbreviations C00 to C88.

  The upper part of FIG. 22 is a diagram showing a basic structure of unit code data U in the embodiment using this two-dimensional encoding table. The basic structure is basically the same as the structure of the unit code data in the embodiment using the one-dimensional encoding table described so far, and is composed of an identification code C and actual data D. If the bit length of the identification code C is a and the bit length of the actual data D is b, the condition “a + b = k × N” (where k is an arbitrary integer) is satisfied. However, the identification code C is a code selected from the two-dimensional encoding table and is a code indicating not only the bit length b of the actual data D but also the run length value R. The run length value R indicates the number of numerical values 0 arranged prior to the actual data D.

  FIG. 23 is a diagram showing a process for performing the encoding method using the two-dimensional encoding table shown in FIG. 22 for the numerical data string shown in FIG. The table shown in the upper part of FIG. 23 is substantially the same as the table shown in the upper part of FIG. 21, but the individual identification codes shown in the column of the identification code C are listed in the two-dimensional encoding table shown in FIG. It is an identification code. In addition, a column of count value J is provided instead of the U bit length column. Here, the count value J is a variable for counting zero run length values, and the initial value is zero.

  In the table shown in the upper part of FIG. 23, the row of data number 1 includes actual data “11100” and numeric data “28” (binary notation with 8-bit fixed length is “00011100”). The identification code “C05” corresponding to the bit length “5” and the count value “J = 0” are shown. The count value J is counted up by +1 when the numerical data D is 0 (however, it is not counted up when it reaches the maximum value Rmax), and the numerical data D is not 0 Is reset to 0 after the identification code C is selected. Since the numerical data of data number 1 is “28”, it is reset to J = 0 after the identification code “C05” is selected. The identification code “C05” is an identification code corresponding to a combination of “bit length b = 5” and “run length value 0” in the two-dimensional encoding table shown in FIG. Here, “bit length b = 5” indicates the bit length of the actual data “11100”, and “run length value 0” indicates the count value J at that time.

  The next row of data number 2 corresponds to the actual data “11111011” and the bit length “8” of the actual data for the numerical data “251” (binary notation with 8-bit fixed length is “11111011”). The identification code “C08” and the count value “J = 0” are shown. Since the numerical data of the data number 2 is “251”, it is reset to J = 0 after the identification code “C08” is selected. The identification code “C08” is an identification code corresponding to a combination of “bit length b = 8” and “run length value 0” in the two-dimensional encoding table shown in FIG. Here, “bit length b = 8” indicates the bit length of the actual data “11111011”, and “run length value 0” indicates the count value J at that time.

  The subsequent row of data number 3 corresponds to the actual data “1” and the bit length “1” of the actual data for the numerical data “1” (binary notation with 8-bit fixed length is “00000001”). An identification code “C01” and a count value “J = 0” are shown. Since the numerical data of the data number 3 is “1”, it is reset to J = 0 after the identification code “C01” is selected. The identification code “C01” is an identification code corresponding to a combination of “bit length b = 1” and “run length value 0” in the two-dimensional encoding table shown in FIG. Here, “bit length b = 1” indicates the bit length of the actual data “1”, and “run length value 0” indicates the count value J at that time.

  On the other hand, in the rows of data numbers 4 to 9, there is no description of the identification code C and the actual data D, and hatched lines are drawn. This is because the unit code data U is basically not created for the numerical data “0”. Thus, when the numerical data is 0, only the count value J is counted up (except when J reaches the maximum value Rmax). Thus, in the rows of data numbers 4-9, only the count value J column is sequentially updated to 1-6.

  The subsequent row of data number 10 corresponds to the actual data “1101” and the bit length “4” of the actual data for the numerical data “13” (binary notation with 8-bit fixed length is “00001101”). An identification code “C64” and a count value “J = 0” are shown. Since the numerical data of the data number 10 is “13”, it is reset to J = 0 after the identification code “C64” is selected. The identification code “C64” is an identification code corresponding to a combination of “bit length b = 4” and “run length value 6” in the two-dimensional encoding table shown in FIG. Here, “bit length b = 4” indicates the bit length of the actual data “1101”, and “run length value 6” indicates the count value J at that time (before reset).

  The next row of data number 11 corresponds to the actual data “11” and the bit length “2” of the actual data for the numerical data “3” (binary notation with 8-bit fixed length is “00000011”). The identification code “C02” and the count value “J = 0” are shown. Since the numerical data of the data number 11 is “3”, it is reset to J = 0 after the identification code “C02” is selected. The identification code “C02” is an identification code corresponding to a combination of “bit length b = 2” and “run length value 0” in the two-dimensional encoding table shown in FIG. Here, “bit length b = 2” indicates the bit length of the actual data “11”, and “run length value 0” indicates the count value J at that time.

  An encoded data string created based on such a process is shown in the lower part of FIG. As shown in the figure, since unit code data U4 to U9 for numerical value 0 of data numbers 4 to 9 are not created, the encoded data string is composed of unit code data U1, U2, U3, U10, U11,. ing. Here, the unit code data U1, U2, U3 correspond to the original numerical data 28, 251, 1, respectively, and the unit code data U10 is the original numerical data 0,0,0,0,0,0,13. The unit code data U11 corresponds to the original numerical data 3. Eventually, the unit code data U10 can be said to be data obtained by encoding not only the numerical value “13” of the data number 10 but also six 0s preceding it. That is, the actual data “1101” portion of the unit code data U10 indicates the numerical value “13”, and the identification code “C64” portion indicates 6 zeros.

  As described above, for a numerical data string in which a large number of zeros are likely to appear in succession, if encoding is performed using a two-dimensional coding table, a large number of zeros can be expressed by one unit code data. As a result, the data capacity can be greatly reduced. In addition, if a table that satisfies the above-described two conditions is used as the two-dimensional encoding table, as in the embodiment using the one-dimensional encoding table described so far, parallel processing is performed when decoding is performed. The merit peculiar to this invention that processing becomes possible is also acquired.

  By the way, in the embodiment described above, the numerical data information indicating 0 is basically included as a run-length value in the identification code of the unit code data created for the subsequent numerical data other than 0. Therefore, it is basically unnecessary to create actual data for numerical data indicating 0, and the minimum value of the bit length b of the actual data is 1. Then, the column of the bit length “b = 0” in the two-dimensional encoding table shown in FIG. 22 should be unnecessary. However, in practice, exceptional processing is required. I will explain this point below.

  The first exception process is a case where numerical data indicating 0 continuously appears exceeding the preset maximum value Rmax of the run length. For example, in the case of the two-dimensional encoding table shown in FIG. 22, since the maximum value Rmax = 8 of the run length value R is set, it is impossible to handle a run length in which the numerical value 0 is 9 or more. Of course, the problem can be solved if the maximum value Rmax can be set to a very large value. However, as the maximum value Rmax is increased, the number of necessary identification codes increases and the bit length of each identification code also increases. It is not preferable. Therefore, in practice, the maximum value Rmax must be suppressed to a certain value.

  Therefore, when numerical data indicating 0 continuously appears exceeding the maximum value Rmax, the following exception processing is performed. For example, consider the case of Rmax = 8. In this case, if a numerical value X that is not 0 comes after the occurrence of 8 zeros in succession, the processing as described above is possible. That is, when the eighth 0 comes, the count value J = 8, and when the unit code data for the ninth numerical value X is created, if the identification code includes the information that the run length value R = 8. Good. However, if the ninth is also 0, the count value J cannot be increased any more, so unit code data is exceptionally created for the ninth 0. In this case, the actual data is a virtual bit string having a bit length of 0, and the generated unit code data is substantially data composed only of an identification code.

  In order to perform such exception processing, an identification code “C80” corresponding to a combination of “bit length b = 0” and “run length value 8” is prepared in the two-dimensional encoding table shown in FIG. It is necessary to keep. The identification code “C80” used for such exception processing is generally called “ZRL (Zero Run Length)”.

  The second exception process is not necessarily a necessary process. However, when the “zero permanent state” in which the numerical data subsequent to the end of the input numeric data string is all zero is confirmed, In this process, a special “end code” indicating “permanent state” is used as an identification code. Such an “end code” is generally called “EOB (End Of Block)”. For convenience, in the two-dimensional coding table, “bit length b = 0” and “run length value 0”. ”Is defined as an identification code corresponding to the combination. Therefore, the identification code “C00” in the two-dimensional encoding table shown in FIG. 22 can be used as this “end code EOB”.

  As described above, in the two-dimensional encoding table shown in FIG. 22, the identification codes C10, C20, C30,..., C70 other than “C00” and “C80” in the “bit length b = 0” column are actually Does not need to be defined.

<<< §10. Changes when using a two-dimensional encoding table >>
In §9, the basic principle of using a two-dimensional encoding table has been described, but here, when using this two-dimensional encoding table, it is necessary to apply to the embodiments described so far. Describe the changes.

<Changes to the encoding method described in §5>
Even when a two-dimensional encoding table is used, there is no change in that the encoding method is to encode a numerical data string composed of fixed-length bits using a variable-length bit string. Then, by generating actual data representing specific numerical data using a variable-length bit string, and adding an identification code having at least information indicating the bit length of the actual data to the head of the actual data, The same is true in that unit code data having information indicating at least the specific numerical data itself is generated, and the plurality of generated unit code data are sequentially arranged and output as an encoded data string. However, the identification code includes not only information indicating the bit length of the actual data but also information indicating the run length value of the numerical value 0 arranged in advance. For this reason, the generated unit code data includes not only information indicating specific numerical data itself as actual data but also information of numerical value 0 arranged in advance.

  Naturally, the biggest difference is that, instead of the one-dimensional encoding table as shown in FIG. 9B, a two-dimensional encoding table as shown in FIG. 22 is used. This two-dimensional encoding table is a table indicating a unique identification code corresponding to a combination of individual bit lengths and individual run length values. Of course, both the one-dimensional coding table and the two-dimensional coding table are coding tables indicating at least “a correspondence relationship between a plurality of bit lengths within a predetermined range and an identification code corresponding to the bit length”. Then it is common. In addition, these tables indicate that “Condition 1: When any of the identification codes in the table is focused, when the bit length of the focused identification code itself is a, the portion of the a bit from the top is the focused “There is no other identification code in the table that is the same as the identification code” and “Condition 2: When the bit length corresponding to the identification code of interest is b, a predetermined reference bit length N (however, N is an integer greater than or equal to 2), and “a + b = k × N” (where k is an arbitrary integer).

  FIG. 24 is a flowchart showing the basic procedure of an encoding method using this two-dimensional encoding table. Each stage of the flowchart shown in FIG. 24 is substantially the same as each stage of the flowchart shown in FIG. The changes are that the two-dimensional encoding table is input at the table input stage of step S12, the point that steps S13A, S13B, and S13C are added after the data extraction stage of step S13, and step S15. In this case, the identification code is selected with reference to the two-dimensional encoding table, and the count value J = 0 is reset after the selection. Hereinafter, these changes will be described.

  First, in step S12, when a predetermined maximum run length value set in advance is Rmax, a plurality of bit lengths within a predetermined range sufficient to represent actual data and a plurality of bit lengths within a range up to Rmax. For each combination of street run length values, a two-dimensional encoding table indicating a correspondence relationship between each combination and a unique identification code corresponding to the combination is input. Of course, this table satisfies the above two conditions.

  At this time, the count value J is assumed to be the initial value 0. Next, when numeric data is extracted in the data extraction stage of step S13, it is determined whether or not the extracted numeric data is data indicating 0 in step S13A. If the extracted numerical data is data indicating 0, the process proceeds to step S13B, and it is determined whether or not the count value J thus far has reached the maximum value Rmax. If the count value does not reach the maximum value Rmax, the process proceeds to step S13C, and a run length value counting step is executed in which the number of times that numerical data indicating 0 is continuously extracted is counted as the run length value R. . Specifically, in step S13C, a process of increasing the count value J by 1 is performed, and the data extraction stage of step S13 is executed again. Eventually, unless the maximum value Rmax is reached, every time a numerical value 0 is extracted, the number of extractions of 0 is counted in step S13C.

  On the other hand, if the extracted numerical data is not data indicating 0, the process proceeds from step S13A to step S14, and actual data is generated. The actual data generation process is as described in §4. For example, when handling signed numeric data, if the extracted numeric data is data indicating a positive value, a variable-length bit string that does not include 0 at the beginning is generated as actual data indicating the numeric data, When the extracted numerical data is data indicating a negative value, a variable-length bit string that does not include 1 at the head is generated as actual data indicating the numerical data.

  Even when the extracted numerical data is data indicating 0 and it is determined in step S13B that the count value J has reached the maximum value Rmax, the actual data generation stage in step S14 is performed as the above-described exception processing. Done. In this case, since the numerical data is 0, a virtual bit string having a bit length of 0 is generated as actual data (actually, no bit string is generated).

  In step S12, since a two-dimensional encoding table is input, in the identification code selection stage in step S15, an identification code is selected with reference to this two-dimensional encoding table. Specifically, the identification code corresponding to the combination of the bit length b of the actual data generated in step S14 and the run length value R (count value J) when the actual data is generated is selected. become. Then, after the identification code is selected, a process of resetting the count value J = 0 is performed. In short, the count value J is reset to 0 each time an identification code is selected and unit code data is generated.

  If it is determined in step S13B that the count value J has reached the maximum value Rmax and actual data is generated in step S14, the bit length of the actual data is 0, and the counter value J = Since it is Rmax, the special identification code “ZRL” for exception processing (the identification code “C80” shown in FIG. 22) is selected as described in §9 in the identification code selection stage of step S15. .

  Finally, in step S17, the process of returning to step S13 is performed until it is determined that the process for all data has been completed. Accordingly, the data extraction stage of step S13 is repeatedly executed for each of the numerical data constituting the input numerical data string, and further, the run length value counting stage of step S13C, the actual data generation stage of step S14, The identification code selection stage of step S15 and the unit code data generation stage of step S16 are repeatedly executed as necessary.

  In addition, as explained in §9, in the case of the “zero persistent state that all the numerical data following the numerical data string including the numerical data to be extracted are all zero”, the zero permanent state When the method of using the “termination code EOB” indicating as an exceptional identification code is adopted, when the numerical data is extracted at the data extraction stage of step S13, “the numerical value including the numerical data to be extracted is included. Execute the investigation process to check whether the numerical data that follows until the end of the data string is “zero persistent state”, and if the investigation process confirms that it is in the zero persistent state, Proceeding to the actual data generation stage of step S14, a virtual bit string having a bit length of 0 is generated as actual data, and in the subsequent identification code selection stage of step S15, B shows a persistent state of "end code EOB" may be selected as the identification code for the exception processing.

<Changes in decryption method described in §6>
Even when a two-dimensional encoding table is used, “at least an identification code indicating a predetermined bit length followed by actual data consisting of a bit string having the bit length, the total length being predetermined. At least individual real data of an encoded data string formed by arranging a plurality of unit code data set so as to be an integral multiple of a reference bit length N (where N is an integer of 2 or more) There is no change in that the decoding method restores the numerical data corresponding to. However, there is a slight difference in that decoding is performed on an encoded data sequence in which the numerical value 0 is expressed as a run length value.

  Therefore, a decoding method using a two-dimensional encoding table is described as follows: “A real code consisting of a bit string having the bit length is arranged following an identification code indicating a combination of a predetermined bit length and a predetermined run length value. A data string in which numerical data corresponding to actual data is arranged after numerical data corresponding to the run length value is arranged after the numerical data indicating 0 is arranged, and the total length is a predetermined reference bit length N (however, N is numerical data indicating 0 and individual data of an encoded data sequence formed by arranging a plurality of unit code data (maximum bit length Umax) set so as to be an integer multiple of 2). It can be said that this is a method of restoring the original data string formed by arranging the actual data.

  The procedure of this decoding method is basically the same as the procedure shown in the flowchart of FIG. 17 described in §6. However, in the table input stage of step S22, a two-dimensional encoding table as shown in FIG. 22 is input instead of the one-dimensional encoding table as shown in FIG. 9B.

  Further, the decoding processing stage in step S24 is slightly different. That is, by parallel processing by M decoding processing units, with reference to the two-dimensional encoding table, the numerical data indicating 0 is enumerated for the number of times corresponding to the run-length value for each distributed partial data, and then the actual data By arranging numerical data corresponding to, a decoding process for restoring the original data string is performed. Then, in the data organization stage of step S25, a decrypted data sequence in which numerical data indicating 0 and numerical data corresponding to individual actual data are arranged by selecting the results of the decoding processing by the M decoding processing units. Is generated.

  It should be noted that in the decoding process stage of step S24, when a special identification code “ZRL” or “end code EOB” for exception processing is recognized, it is necessary to perform exception processing according to the identification code. That is, when the identification code “ZRL” is recognized, the process of arranging the numerical values 0 of “Rmax + 1” when the maximum run length defined in the two-dimensional encoding table is Rmax. There is a need to do. Further, when the “termination code EOB” is recognized, it is necessary to perform a process of arranging the numerical values 0 until a predetermined data length is reached.

<Changes to encoding apparatus described in §7>
In §7, the basic configuration of the encoding apparatus according to the present invention was described with reference to FIG. The basic configuration of an encoding device that uses a two-dimensional encoding table is substantially the same as the configuration shown in the block diagram of FIG. However, as a matter of course, the table storage unit 120 stores a two-dimensional encoding table indicating unique identification codes corresponding to combinations of individual bit lengths and individual run length values. This two-dimensional encoding table has a plurality of bit lengths within a predetermined range sufficient for expressing actual data and a range up to Rmax when Rmax is a predetermined maximum run length value determined in advance. It is a table which shows the correspondence of each combination and the specific identification code corresponding to the said combination about each combination of these multiple run length values.

  Further, the processing performed by the actual data generation unit 140 is slightly changed. For example, in the case of handling signed numeric data, if the extracted numeric data is data indicating 0 and the count value so far has not reached the maximum value Rmax, the numeric data indicating 0 If the extracted numeric data is data indicating a positive value, the leading zero is not included as actual data indicating the numeric data. Processing for generating a variable-length bit string, and processing for generating a variable-length bit string that does not include a leading 1 as actual data indicating the numeric data when the extracted numeric data is data indicating a negative value When the extracted numerical data is data indicating 0 and the count value has reached the maximum value Rmax, a virtual bit string having a bit length of 0 is converted to actual data. Processing may be performed to generate a.

  On the other hand, the identification code selection unit 150 refers to the two-dimensional encoding table stored in the table storage unit 120, and generates the bit length of the actual data and the run length value when the actual data is generated. The identification code corresponding to the combination is selected, and the count value is reset to 0 after selection. At this time, for the combination of “bit length b = 0” and “run length value R = Rmax”, the special identification code “ZRL” for exception handling described above is selected.

  When the above-mentioned “termination code EOB” is used, when the data extraction unit 130 extracts the numerical data, the “numerical value subsequent to the end of the numerical data string including the numerical data to be extracted” is displayed. When the actual data generation unit 140 confirms that the data is in the zero-permanent state by performing the investigation process to check whether or not the data is “zero-permanent state that all data is 0”, the bit length Is generated as actual data, and when the identification code selection unit 150 confirms that the zero-permanent state is obtained by this investigation process, “termination code EOB” indicating the zero-permanent state. May be selected as the identification code.

<Changes to the decoding device described in §8>
In §8, the basic configuration of the decoding device according to the present invention was described with reference to FIG. The basic configuration of a decoding apparatus that uses a two-dimensional encoding table is almost the same as the configuration shown in the block diagram of FIG. However, as a matter of course, the table storage unit 220 stores a two-dimensional encoding table indicating unique identification codes corresponding to combinations of individual bit lengths and individual run length values.

  The decoding device has a structure in which “the identification code indicating a combination of a predetermined bit length and a predetermined run length value is followed by real data including a bit string having the bit length, Represents a data string in which numerical data corresponding to the actual data are arranged after being enumerated a number of times corresponding to the run length value, and the total length is a predetermined reference bit length N (where N is an integer of 2 or more) ), Numerical data indicating 0 and individual actual data are arranged for an encoded data string configured by arranging a plurality of unit code data (maximum bit length Umax) set to be an integral multiple of “). This means a device having a function of restoring the original data string.

  Further, the M decoding processing units 240 (1) to 240 (M) in this apparatus refer to the two-dimensional encoding table stored in the table storage unit 220, and 0 for each distributed partial data. After the numerical data representing the number of times corresponding to the run length value are arranged, the numerical data corresponding to the actual data are arranged, thereby performing a decoding process for restoring the original data string. Then, the data organization unit 250 selects the results of the decryption processing by the M decryption processing units 240 (1) to 240 (M), and numerical data indicating 0 and numerical data corresponding to individual actual data A decrypted data string in which is arranged is generated.

  When the special identification code “ZRL” or “termination code EOB” for exception processing is recognized in the decryption processing units 240 (1) to 240 (M), exception processing corresponding to the identification code is performed. Have a function to do. That is, when the identification code “ZRL” is recognized, the process of arranging the numerical values 0 of “Rmax + 1” when the maximum run length defined in the two-dimensional encoding table is Rmax. To do. Further, when the “end code EOB” is recognized, this is reported to the data organization unit 250, and the data organization unit 250 determines a predetermined data length (for example, JPEG image data described later). In the case of the AC component, the process of arranging numerical values 0 is performed until the total of 63 numerical data) is reached, and the decoding process for the encoded data sequence S is terminated.

<Changes to encoded data file>
FIG. 15 shows an example of the structure of the encoded data file F created by the encoding method according to the present invention. When encoding is performed using a two-dimensional encoding table, the contents of the data file F are shown. Will be slightly different. That is, the data file F has a structure in which “the identification code indicating a combination of a predetermined bit length and a predetermined run length value is followed by actual data including a bit string having the bit length,” This is a data string in which numerical data corresponding to the actual data is arranged after the numerical data indicating 0 is enumerated the number of times corresponding to the run length value, and the total length is a predetermined reference bit length N (where N is 2 or more) It corresponds to bit sequence data configured by arranging multiple unit code data (maximum bit length Umax) of different lengths set to be an integer multiple of (integer) and individual identification codes A two-dimensional encoding table T indicating a combination of a specific bit length and a specific run length value is accommodated.

  Here, the two-dimensional encoding table T is a table used for an encoding method for encoding a numeric data string using a variable-length bit string, and a plurality of bit lengths within a predetermined range and a plurality of bits within a predetermined range. For each run-length value, the correspondence between each bit length and each run-length value and the unique identification code corresponding to that combination is shown. Even when attention is paid to the identification code, another identification code in which the a-bit portion from the head is the same as the target identification code when the bit length of the target identification code itself is a is included in this table. “A + b = k × N” (provided that a predetermined reference bit length N (where N is an integer equal to or greater than 2) is n, where b is the bit length corresponding to the identification code of interest. , K will be referred to the table that satisfy an arbitrary integer) The condition.

  On the other hand, FIG. 16 shows another example of the structure of the encoded data file F created by the encoding method according to the present invention. When encoding is performed using a two-dimensional encoding table, this data The contents of file F will also be slightly different. That is, the data file F has a structure in which “the identification code indicating a combination of a predetermined bit length and a predetermined run length value is followed by actual data including a bit string having the bit length,” This is a data string in which numerical data corresponding to the actual data is arranged after the numerical data indicating 0 is enumerated the number of times corresponding to the run length value, and the total length is a predetermined reference bit length N (where N is 2 or more) It corresponds to bit sequence data configured by arranging multiple unit code data (maximum bit length Umax) of different lengths set to be an integer multiple of (integer) and individual identification codes Table specifying information H for specifying a two-dimensional encoding table indicating a combination of a specific bit length and a specific run length value is accommodated.

<Handling non-zero run length>
All of the examples described so far are examples in which consecutive 0s included in the numerical data string are expressed as run lengths. In general, image data often includes consecutive zeros. In particular, in the case of image data in the JPEG format described later, a large number of consecutive zeros are included. However, the encoding method using the two-dimensional encoding table according to the present invention is not necessarily limited to the method of expressing the numerical value 0 as a run length, and also when expressing an arbitrary numerical value X as a run length. Applicable.

  For example, when a numeric data string to be encoded includes a large number of consecutive portions of a specific numerical value X, encoding that expresses the specific numerical value X as a run length instead of the numerical value 0 is performed. Efficient. In this case, for the numerical value 0, normal expression (representation as actual data, not run length) is performed, and for the numerical value X, the number of consecutive appearances is counted and encoded as a run length value. What should I do?

  Further, it is possible to express an arbitrary numerical value X as a run length by using the “method of expressing 0 as a run length” described in §9 as it is. Specifically, all the group of numerical data to be encoded may be encoded by the method described in §9 after performing a process of subtracting X in advance. Further, when performing decoding, after performing decoding by the method described in §9, a process of adding X may be performed.

  For example, when encoding data that frequently continues with the numerical value “7”, first, a process of subtracting “7” from all data is performed. With this processing, the numerical value “7” is converted into the numerical value “0”, and therefore, the continuous portion of the numerical value “7” is converted into the continuous portion of the numerical value “0”. Therefore, if encoding is performed by the method described in §9, a continuous portion of the numerical value “0” (originally a continuous portion of the numerical value “7”) is expressed by a run length. On the other hand, when decoding is performed, a process of adding “7” to the decoded data obtained by the method described in §9 is performed, so that the original correct numerical value can be restored. become.

  Of course, the process of adding X in advance may be performed at the time of encoding, and the process of subtracting X may be performed at the time of decoding. If subtraction or addition is performed, the number of bits increases (for example, a numerical value in the range of −127 to +127 can be expressed in 8 bits (1's complement expression)), but “7” When subtracting, it becomes a value in the range of -134 to +120, so 9 bits are required.) To avoid this, rotate the value that protrudes from the lower limit of the original range and rotate it to the upper limit, It is only necessary to rotate the numerical value protruding from the upper limit and rotate it to the lower limit (for example, in the above example, −134 is replaced with +121, −133 is replaced with +122,..., −128 is replaced with +127. And the numerical range will be -127 to +127 as before).

<<<< §11. Application to JPEG images >>>
Here, an embodiment in which the encoding / decoding method according to the present invention is applied to a JPEG image will be described. The JPEG method is widely used in computers and digital cameras as one method for compressing still image data. An image compressed by this method is generally called a JPEG image.

  FIG. 25 is a block diagram showing a configuration of a general JPEG image compression / decompression processing apparatus. In order to perform JPEG compression, first, one image is divided into fixed-size blocks of 8 × 8 pixels, and processing is performed in units of 8 × 8 pixel blocks.

  The compression processing apparatus 300 for JPEG images includes a DCT unit 310, a quantization unit 320, and an encoding unit 330, as shown in the figure. The DCT unit 310 performs a process of transforming the data X of the 8 × 8 pixel block from the spatial domain to the frequency domain using a discrete cosine transform (DCT). Subsequently, the quantization unit 320 reduces the amount of information, and the encoding unit 330 performs encoding for data compression to obtain compressed data Y.

  On the other hand, the JPEG image decompression processing apparatus 400 includes a decoding unit 410, an inverse quantization unit 420, and an inverse DCT unit 430 as shown in the figure. Each of these units has a function of performing processing opposite to that of the encoding unit 330, the quantization unit 320, and the DCT unit 310 in the compression processing apparatus 300. Therefore, the reverse process of compression is performed on the compressed data Y, and the original data 8 × 8 pixel block X is obtained.

  The present invention can be applied to the encoding unit 330 and the decoding unit 410 in such an apparatus that performs JPEG image compression / decompression processing. A specific application example will be briefly described below.

  When the quantization process of the quantization unit 320 shown in FIG. 25 is completed, one pixel at the upper left of all 64 pixels constituting the quantized 8 × 8 pixel block has a DC component pixel value, and the remaining 63 pixels Has the pixel value of the AC component. FIG. 26 is a plan view showing a pixel array constituting the 8 × 8 pixel block after such quantization. The value of each pixel constituting this pixel array is a pixel value after DCT processing, not the pixel value of the original image. Therefore, to be precise, it is a value that should be called a “DCT coefficient”, not a “pixel value”. However, in the following description, these values are also referred to as “pixel values” for convenience. The pixel described as “DC” in the figure is a pixel having a DC component pixel value, and the other 63 pixels are pixels having an AC component pixel value. The AC component is information indicating the frequency component of the pixel value, and the DC component is information indicating the average of the pixel values of the 8 × 8 pixel block.

  When encoding data constituting such an 8 × 8 pixel block, a zigzag scan process is performed on the AC component as illustrated. That is, the 63 pixels having the pixel value of the AC component are rearranged in the order indicated by the arrows in the drawing. This is because, when the discrete cosine transform is performed by the DCT unit 310, the lower frequency components gather near the upper left corner of the block, and the higher frequency components gather near the lower right corner of the block. When rearrangement is performed by zigzag scan processing as shown in the figure, 63 pixels having pixel values of AC components are rearranged in order from low frequency components to high frequency components.

  Let us illustrate the above process with specific examples. FIG. 27 is a plan view illustrating an example of a pixel value distribution of a quantized pixel block that is a target of JPEG compression processing. Here, the pixel value “20” of the upper left pixel is a value indicating the DC component, and each of the remaining 63 pixels is a value indicating the AC component. FIG. 28 is a diagram showing numerical data of DC components and AC components extracted from the pixel block shown in FIG. The numerical data of the DC component is only “20” as shown in FIG. 28A, and is expressed by 12-bit data including the sign bit. On the other hand, the numerical data of the AC component becomes 63 numerical data strings as a result of rearrangement by the zigzag scanning process, and is expressed by 11-bit data including the sign bit, respectively. Is supposed to.

  Both the numerical data of the DC component and the numerical data of the AC component are numerical values having a sign (for example, in the example shown, the numerical value “−2” is negative data). In the figure, for convenience of explanation, each numerical data is shown in decimal notation. Actually, however, the numerical data of the DC component is given as an 11-bit fixed length bit string excluding the sign bit, and the numerical value of the AC component. Data is given as a 10-bit fixed-length bit string excluding the sign bit.

  Here, since the numerical data of the DC component shown in FIG. 28 (a) is data extracted only for one block, when encoding into a variable length bit string, a one-dimensional encoding table is used. It is sufficient to use it. On the other hand, the numerical data of the AC component shown in FIG. 28B is obtained as 63 continuous data for one block, and there is a high possibility that 0 appears continuously. In particular, there is a high possibility that 0 will continue in the second half showing the high frequency component. Therefore, it is preferable to use a two-dimensional encoding table when encoding the numerical data of the AC component into a variable length bit string.

  Therefore, as the encoding means 330 of the JPEG image compression processing apparatus 300 shown in FIG. 25, the encoding apparatus using the one-dimensional encoding table described so far for the part that encodes the numerical data of the DC component. For the part that encodes the numerical data of the AC component, the encoding device using the two-dimensional encoding table described so far may be used. Similarly, as the decoding unit 410 of the JPEG image decompression processing apparatus 400, the decoding apparatus using the one-dimensional encoding table described so far is adopted for the part that decodes the numerical data of the DC component. For the part that decodes the numerical data of the AC component, the decoding device that uses the two-dimensional encoding table described so far may be employed.

  FIG. 29 is a diagram illustrating an example of a DC component encoding table (one-dimensional encoding table) used for encoding numerical data of DC components. As shown in the figure, an identification code C is defined for each of the bit lengths b = 0 to 11. The broken line column on the right side of the table shows the bit length a of each identification code C and the bit length “a + b” of the unit code data U created using the identification code C for reference. As shown in the figure, the bit length “a + b” of U corresponds to any of 4, 8, 12, 16, and 20. This indicates that when N = 4, the condition “a + b = k × N” (where k is an arbitrary integer) is satisfied.

  Of course, this encoding table is “when any identification code in this table is focused, when the bit length of the focused identification code itself is a, the a-bit part from the beginning is the focused identification code. There is also a condition required for the variable length coding table that there is no other identification code in the table that is the same as

  FIG. 30 is a diagram showing a result of encoding the DC component shown in FIG. 28 using the table shown in FIG. With respect to the numerical value “20”, the actual data D from which redundant bits are deleted is “10100”, and the identification code C corresponding to the data length “5” is “010” when referring to the table of FIG. Therefore, the numerical data “20” of the DC component is converted into 8-bit encoded data “01010100” as shown in FIG.

  On the other hand, FIG. 31 is a diagram illustrating an example of an AC component encoding table (two-dimensional encoding table) used for encoding numerical data of AC components. As shown in the figure, an identification code C is defined for each combination of the range of the bit length b = 0 to 10 and the range of the run length value R = 0 to 15. In the two-dimensional encoding table shown in FIG. 22, for the sake of convenience of explanation, individual identification codes are indicated by abbreviations C00 to C88. However, in the table shown in FIG. 31, each identification code is indicated by an actual bit string. . The identification code “0010” in the column of bit length b = 0 is the “end code EOB” for exception processing described above, and the identification code “0101” is “ZRL” for exception processing described above.

  Of course, the table shown in FIG. 31 also indicates that “a bit of the identification code itself has a bit length from the beginning when the identification code in the table is focused. It satisfies the condition required for the variable length coding table that “another identification code that is the same as the identification code does not exist in this table”, and “the bit length corresponding to the target identification code” Where b is a predetermined reference bit length N (where N is an integer of 2 or more), the condition “a + b = k × N” (where k is an arbitrary integer) ”is satisfied. Specifically, since N = 4 is set, the bit length of the unit code data U is a multiple of 4, such as 4, 8, 12, 16, 20, 24.

  FIG. 32 is a diagram showing a process of encoding the AC component shown in FIG. 28 using the table shown in FIG. The configuration of the table shown in FIG. 32 is the same as the configuration of the table shown in the upper part of FIG. 23. For each numerical data D, an identification code C, actual data D (unit code code U), and a count value J are included. It is shown. The count value J is a variable for counting zero run length values. In this table, 63 pieces of numerical data D to which data numbers 1 to 63 are attached are 63 pieces of AC component numerical data (10-bit fixed-length bit string) shown in FIG. Hereinafter, the table of FIG. 32 will be viewed from the top.

  First, the row of data number 1 corresponds to the actual data “101” and the bit length “3” of this actual data for numeric data “5” (binary notation with a 10-bit fixed length is “0000000101”) ” The identification code “01100” and the count value “J = 0” are shown. As described above, the count value J is incremented by +1 when the numerical data D is 0 (however, it is not counted up when the maximum value Rmax = 15). Is not 0, it is reset to 0 after the identification code C is selected. Since the numerical data of the data number 1 is “5”, it is reset to J = 0 after the identification code “01100” is selected. The identification code “01100” is an identification code corresponding to a combination of “bit length b = 3” and “run length value 0” in the two-dimensional encoding table shown in FIG. Here, “bit length b = 3” indicates the bit length of the actual data “101”, and “run length value 0” indicates the count value J at that time.

  In the next row of data number 2, the numeric data is “0” (binary notation with a 10-bit fixed length is “0000000”). Therefore, selection of the identification code C and creation of the actual data D are not performed. The code data U is not created. Instead, the count value J is counted up to J = 1. Similarly, in the rows of data numbers 3 and 4, the count value J is counted up to J = 2 and J = 3, respectively.

  In the subsequent line of data number 5, the numerical data is “37” (binary notation with a 10-bit fixed length is “0000100101”) ”, and thus actual data“ 100101 ”is created. Based on the bit length b = 6 of the actual data and the count value J = 3 at that time, the corresponding identification code “1111011000” is selected by referring to the table of FIG. 31, and the count value is J = Reset to zero.

  In the next row of data number 6, since the numerical data is “0”, selection of the identification code C and creation of the actual data D are not performed, and the unit code data U is not created. Instead, the count value J is counted up to J = 1.

  In the subsequent row of data number 7, the numerical data is “23” (binary notation with a 10-bit fixed length is “0000010111”) ”, so actual data“ 10111 ”is created. Based on the bit length b = 5 of the actual data and the count value J = 1 at that time, the corresponding identification code “1011111” is selected by referring to the table of FIG. 31, and the count value is J = Reset to zero.

  In the next rows of data numbers 8 to 13, since the numerical data is “0” in all cases, selection of the identification code C and creation of the actual data D are not performed, and the unit code data U is not created. Instead, the count value J is sequentially counted up, and finally J = 6.

  In the subsequent line of data number 14, since the numerical data is “−2” (binary notation with a 10-bit fixed length is “1111111101”), actual data “01” is created. Based on the bit length b = 2 of the actual data and the count value J = 6 at that time, the corresponding identification code “101100” is selected by referring to the table of FIG. 31, and the count value is J = Reset to zero.

  In the next rows of data numbers 15 to 16, since numerical data is “0” in all cases, selection of identification code C and creation of actual data D are not performed, and unit code data U is not created. Instead, the count value J is sequentially counted up, and finally J = 2.

  In the subsequent line of data number 17, the numerical data is “9” (binary notation with a 10-bit fixed length is “0000001001”) ”, and thus actual data“ 1001 ”is created. Based on the bit length b = 4 of the actual data and the count value J = 2 at that time, the corresponding identification code “11010000” is selected by referring to the table of FIG. 31, and the count value is J = Reset to zero.

  In the next row of data number 18, the numerical data is “0”, but thereafter, until the data number 63, “zero permanent state” in which the numerical data is all “0” is confirmed. Therefore, by referring to the table of FIG. 31, the identification code “0010” corresponding to “termination code EOB” is selected, and the process is terminated there.

  Thus, the AC component numerical data consisting of a total of 63 fixed-length bits shown in FIG. 28 (b) is converted into an encoded data string consisting of variable-length bits as shown in FIG. Here, each bit string shown in the 1st to 6th rows in FIG. 33 corresponds to the unit code data U in the 1st, 5th, 7th, 14th, 17th and 18th rows in the table of FIG. The number in parentheses indicates the data length. The actually obtained encoded data string is a string of a total of 60 bits obtained by concatenating all the bit strings shown in FIG. Of course, the bit string is not delimited at all, but the data length of each unit code data is a multiple of 4, as indicated by the numbers in parentheses, and can be decoded by parallel processing unique to the present invention. It has a suitable shape.

  FIG. 34 is a diagram showing the principle of decoding the encoded data sequence shown in FIG. 33 by parallel processing by seven decoding processing units using the decoding method according to the present invention. The figure shows a state in which partial data of 24 bits is distributed to each of seven units Q1 to Q7. The numerical values in parentheses shown below the reference signs Q1 to Q7 indicating each unit indicate that the partial data distributed to each unit is in what bit from the beginning of the original data (60-bit data shown in FIG. 33). It shows whether it corresponds. For example, data of 1 to 24 bits from the head is distributed to the unit Q1, and data of 5 to 28 bits from the head is distributed to the unit Q2. In this example, since the reference bit length N = 4 is set, partial data at a position shifted by 4 bits is distributed to each unit.

  FIG. 35 is a diagram showing a decoding process performed by the seven units Q1 to Q7 that have received the partial data distribution. The decoding process is performed by referring to the AC component code table shown in FIG.

  For example, in the unit Q1, if a matching identification code is searched with reference to the table while increasing the comparison target bit by bit from the beginning, the bit string “01100” becomes “b = 3, R = 0”. Matches the corresponding identification code. Therefore, the subsequent 3 bits “101” are recognized as actual data, and the numerical value “5” is successfully restored. Since the subsequent bit string “1111011000” matches the identification code corresponding to “b = 6, R = 3”, the subsequent 6-bit “100101” is recognized as actual data, and the numerical value “37” is restored. To succeed. Further, according to the run length value R = 3, a process of arranging the numerical value “0” three times before the numerical value “37” is performed. Eventually, the processing result is [5] [0] [0] [0] [37], P1 = 24, as shown on the right side of the figure.

  In the unit Q2, the bit string “0101” matches the identification code corresponding to [ZRL]. As described above, this identification code is an identification code for performing exception processing, and means a process of arranging numerical values “0” by “Rmax + 1”. In the case of the table shown in FIG. 31, since Rmax = 15, the process of arranging 16 numerical values “0” is performed after all. Subsequently, the bit string “1111011000” matches the identification code corresponding to “b = 6, R = 3”. Therefore, the subsequent 6-bit “100101” part is recognized as actual data, and the numerical value “37” is successfully restored. Further, according to the run length value R = 3, a process of arranging the numerical value “0” three times before the numerical value “37” is performed. After that, normal decryption processing cannot be performed, and the processing result is [0] × 16 [0] [0] [0] [37] [ERR], P2 = 20 as shown on the right side of the figure. Become.

  In the unit Q3, the bit string “1111011000” matches the identification code corresponding to “b = 6, R = 3”. Therefore, the subsequent 6-bit “100101” part is recognized as actual data, and the numerical value “37” is successfully restored. Further, according to the run length value R = 3, a process of arranging the numerical value “0” three times before the numerical value “37” is performed. However, after that, normal decoding processing cannot be performed, and the processing result is [0] [0] [0] [37] [ERR], P3 = 16 as shown on the right side of the figure.

  In the unit Q4, the bit string “01100” matches the identification code corresponding to “b = 3, R = 0”. Therefore, the subsequent 3-bit “010” portion is recognized as actual data, and the numerical value “−5” is successfully restored. Since the subsequent bit string “0101” matches the identification code corresponding to [ZRL], the process of arranging 16 numerical values “0” is performed. The next bit string “1011111” matches the identification code corresponding to “b = 5, R = 1”. Therefore, the subsequent 5-bit “10111” portion is recognized as actual data, and the numerical value “23” is successfully restored. Further, according to the run length value R = 1, a process of arranging the numerical value “0” once before the numerical value “23” is performed. The processing result is [−5] [0] × 16 [0] [23], P4 = 24, as shown on the right side of the figure.

  In the unit Q5, the bit string “0010” matches the identification code corresponding to the “termination code EOB”. As described above, this identification code is an identification code for performing exception processing in the zero-permanent state, and indicates that a numerical value “0” is arranged up to the end of the numerical data string. Therefore, at the stage where this “end code EOB” is recognized, the unit Q5 normally ends the process. Therefore, the processing result is [EOB], P5 = 4 as shown on the right side of the figure.

  In the unit Q6, since the bit string “0101” matches the identification code corresponding to [ZRL], first, processing for arranging 16 numerical values “0” is performed. The next bit string “1011111” matches the identification code corresponding to “b = 5, R = 1”. Therefore, the subsequent 5-bit “10111” portion is recognized as actual data, and the numerical value “23” is successfully restored. Further, according to the run length value R = 1, a process of arranging the numerical value “0” once before the numerical value “23” is performed. Since the subsequent bit string “101100” matches the identification code corresponding to “b = 2, R = 6”, the subsequent 2-bit “01” portion is recognized as actual data, and the numerical value “−2” Successful restoration. Further, according to the run length value R = 6, a process of arranging the numerical value “0” six times before the numerical value “−2” is performed. The processing result is [0] × 16 [0] [23] [0] × 6 [−2], P6 = 24, as shown on the right side of the figure.

  In the unit Q7, the bit string “1011111” matches the identification code corresponding to “b = 5, R = 1”. Therefore, the subsequent 5-bit “10111” portion is recognized as actual data, and the numerical value “23” is successfully restored. Further, according to the run length value R = 1, a process of arranging the numerical value “0” once before the numerical value “23” is performed. Since the subsequent bit string “101100” matches the identification code corresponding to “b = 2, R = 6”, the subsequent 2-bit “01” portion is recognized as actual data, and the numerical value “−2” Successful restoration. Further, according to the run length value R = 6, a process of arranging the numerical value “0” six times before the numerical value “−2” is performed. However, after that, normal decoding processing cannot be performed, and the processing result is [0] [23] [0] × 6 [−2] [ERR], P7 = 20 as shown on the right side of the figure. Become.

  The above is the decoding processing executed as parallel processing of the seven units Q1 to Q7. The data organization unit selects a result of the decoding process by each of these units and generates a decoded data string. That is, first, with unit Q1 as the adopted unit, it is recognized that the final bit that has been normally decoded is the 24th bit based on the normal processing bit length P1 = 24 reported from this unit Q1. Then, another unit Q7 to which the partial data having the 25th bit as the first bit is distributed is determined as a new adopted unit. Further, based on the normal processing bit length P7 = 20 reported from the adopted unit Q7, it is recognized that the last bit that has been normally decoded is the 44th bit, and the 45th bit is the first bit. Although another unit to which the partial data is distributed is tried to be a newly selected unit, the corresponding unit is not found, and the first parallel processing is completed.

  Thus, the two units Q1 and Q7 are determined as the adopted units. A unit marked with “◎” at the right end of FIG. 35 is an accepted unit, and a unit marked with “x” is a rejected unit. The data organization unit collects numerical data that has been normally decoded by each of the adopted units Q1 and Q7, and generates a decoded data string by arranging these numerical data. In the case of the illustrated example, [5] [0] [0] [0] [37] [0] [23] [0] [0] [0] [0] [0] [0] [-2] A numeric data string is generated.

  At this time, the total value “44” of the normal processing bit lengths P1 and P7 reported from each of the adopted units Q1 and Q7 to the data distribution unit from the data organization unit is used as information indicating the already-decoded unit. Processing to report is performed. This indicates that the decoding from the head to the 44th bit of the data consisting of all 60 bits shown in FIG. 33 has been completed by the first parallel processing described above. Therefore, the data distribution unit executes a new distribution process for the undecoded units after the 45th bit for the second parallel processing.

<<<< §12. Creation of Huffman coding table >>
As already described with reference to FIG. 8, the variable length coding table created in consideration of the appearance frequency of the bit length b is generally called a Huffman coding table, and the coding using this Huffman coding table is , Called Huffman coding. In the Huffman coding table, the higher the appearance frequency of the bit length b of the actual data, the more the identification code having the shorter bit length a is associated. Therefore, the data compression efficiency is further improved by the Huffman coding. Can do. For this reason, a Huffman coding table is employed in many data compression processes in practice such as the above-described JPEG image compression process.

  The encoding table used in the implementation of the present invention is not necessarily a Huffman encoding table. However, in practice, it is preferable to use the Huffman encoding table in order to improve data compression efficiency.

  The Huffman encoding method according to the present invention converts a numerical data sequence consisting of fixed-length bits into an encoded data sequence consisting of variable-length bits using at least a Huffman encoding table indicating the correspondence between the bit length and the identification code. A Huffman encoding method for encoding is characterized in that, as a Huffman encoding table, when a bit length of an identification code itself is a and a bit length corresponding to the identification code is b, a predetermined reference bit length For N (where N is an integer equal to or greater than 2), a table that satisfies the condition of “a + b = k × N” (where k is an arbitrary integer) is used.

  In addition, the Huffman decoding method according to the present invention uses a Huffman encoding table that indicates that the arithmetic processing device at least uses a Huffman encoding table that indicates a correspondence relationship between a bit length and an identification code. A Huffman decoding method for decoding into a numerical data string consisting of bits, the feature of which is that when the bit length of the identification code itself is a and the bit length corresponding to the identification code is b as a Huffman encoding table In addition, a table that satisfies a condition of “a + b = k × N” (where k is an arbitrary integer) for a predetermined reference bit length N (where N is an integer of 2 or more) is used. .

  As already described in section 2, since the above condition can secure a certain degree of freedom by an arbitrary integer k, it is possible to create a Huffman coding table that satisfies the above condition. Since the Huffman coding table is a table created in consideration of the appearance frequency of the bit length b for a specific numerical data string, it can be said to be a table specialized for encoding the specific numerical data string. In other words, it is a table that can be defined for the first time when a numerical data string to be encoded is given. Therefore, when the Huffman coding table is used in the present invention, first, an existing standard coding table is prepared, and the Huffman coding table is created by performing processing for replacing the contents of the standard coding table. It is preferable to do so.

  FIG. 36 is a block diagram showing a basic configuration of an encoding apparatus using the Huffman encoding table according to the present invention. The coding apparatus shown in FIG. 36 is obtained by adding a frequency counting unit 180 and a table correction unit 190 to the coding apparatus shown in FIG.

  The frequency counting unit 180 has a function of counting the appearance frequency of the bit length b of the actual data for the numerical data string E stored in the data storage unit 110. Since the bit length b of the actual data is uniquely determined based on the value of the numerical data, in practice, a ballot box is provided for each individual bit length b to correspond to the value of each numerical data. If the process of voting on the voting box to be performed is performed, the total value of the appearance frequency can be obtained.

  On the other hand, the table correction unit 190 performs a correction by exchanging the contents of the existing standard encoding table stored in advance in the table storage unit 120, and stores the corrected encoding table in the table storage unit. have. Specifically, the bit length b of the actual data appears by exchanging the table contents for the bit lengths b having an integral multiple difference of the reference bit length N in the existing standard encoding table. As the frequency is higher, a process of generating a modified encoding table associated with an identification code having a shorter bit length a is performed.

  The corrected encoding table newly stored in the table storage unit 120 by the table correction unit 190 has a shorter bit length a as the appearance frequency of the bit length b of the actual data increases. This is a Huffman coding table associated with an identification code. Therefore, the encoded data file F output from the data output unit 170 includes the encoded data sequence S encoded using the Huffman encoding table and the Huffman encoding table itself or the Huffman encoding table. Table specifying information to be specified (for example, a URL indicating the location of the Huffman coding table) is accommodated.

  Here, an example of creating a Huffman coding table will be described below with respect to the application example to the JPEG image described in §11. Assume that a table as shown in FIG. 29 is stored in advance in the table storage unit 120 as a standard coding table for DC components. On the other hand, suppose that the data storage unit 110 stores image data to be compressed by the JPEG method, which is a collection of many 8 × 8 pixel blocks. In this case, the frequency counting unit 180 performs the above-described frequency counting process for individual numerical data constituting the image data. Here, for example, it is assumed that the frequency count result as shown in the table of FIG. 37 is obtained.

  In the case of a normal variable length coding table, a Huffman coding table can be obtained by sorting the contents of the standard coding table based on the frequency count result shown in FIG. Specifically, the shortest identification code “00” in the standard encoding table shown in FIG. 29 may be assigned to the bit length b = 5 in which the vote with the highest appearance frequency “220” is obtained. Similarly, for the bit length b = 6 in which a vote with the second highest appearance frequency “209” is obtained, the second shortest identification code “011” or “010” in the standard encoding table shown in FIG. ". In short, after the bit lengths b are sorted in the order of appearance frequency, an operation of assigning in order from a short identification code may be performed.

  However, in the case of the variable length coding table according to the present invention, when the bit length of the identification code itself is a and the bit length corresponding to the identification code is b, a predetermined reference bit length N (where N is Since the restriction that the condition “a + b = k × N” (where k is an arbitrary integer) is satisfied is imposed on (an integer of 2 or more), the sort operation as described above cannot be performed. However, as described in §2, even if two identification codes whose corresponding bit length b difference is an integer multiple of N (N = 4 in this example) are replaced, “a + b = k × N” The condition remains.

  For example, since the difference between the bit lengths b = 2 and b = 6 shown by the thick frame in FIG. 37 is 4, the identification code corresponding to b = 2 and b = 6 correspond to each other as shown in FIG. Even if the identification code is replaced, the above condition is maintained. In the case of the standard encoding table shown in FIG. 29, the identification code corresponding to b = 6 is a 6-bit code “101100”, but if the replacement shown in FIG. 38 is performed, the identification code corresponding to b = 6 Is corrected to a 2-bit code “00”. That is, a shorter identification code is assigned to b = 6 having a high appearance frequency.

  Thus, although the limitation that the identification codes that can be exchanged with each other is limited to “two identification codes in which the difference between the corresponding bit lengths b is an integer multiple of N” is imposed, such a limitation is imposed. In such a range, after the bit lengths b are sorted in the order of appearance frequency, an operation of assigning in order from a short identification code may be performed. Specifically, for example, after sorting the identification codes with bit lengths b = 0, 4, and 8 as one group in the order of appearance frequency, the identification codes associated with these are reassigned so as to be shorter in the sorting order. Just work. The same operation is performed for the bit length b = 1, 5, 9 group, the bit length b = 2, 6, 10 group, and the bit length b = 3, 7, 11 group. Is obtained.

  Thus, in the present invention, the condition that "the higher the appearance frequency of the bit length b of actual data is, the more the identification code having a shorter bit length a is associated" “a + b = k × N” (where k is an arbitrary value) with respect to a predetermined reference bit length N (where N is an integer of 2 or more), where a is the bit length corresponding to the identification code It should be a sub-condition when the main condition is the condition of That is, the sub-condition is a subordinate condition that should be additionally satisfied while giving priority to the main condition. Therefore, in actuality, when any two identification codes are compared, there may be a case where the sub-condition “the shorter the bit frequency b of the corresponding actual data is, the shorter” is not satisfied. Therefore, the coding table corrected by the above-described replacement work may not be called a “Huffman coding table” in a strict sense, but is referred to as a “Huffman coding table” here for convenience.

  Originally, the “Huffman code” is a code defined by creating a binary tree called “Huffman code tree” in the order of appearance frequency. In a strict sense, “the average code length is minimum and the appearance frequency is It is defined as “higher, shorter code”. However, in practice, various variations have come to be used in various application fields, and codes that do not necessarily satisfy the condition of “minimum average code length”, or “necessarily shorter as the appearance frequency is higher”. The code is expanded to a code that does not satisfy the above condition, and is generally called “Huffman code” (for example, in the field of handling JPEG images, a code that does not consider the appearance frequency at all is also called “Huffman code”) There).

  Therefore, in the present application, “when any identification code in the table is focused, when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. No other identification code such as this exists in this table "and was finally encoded in consideration of the filing frequency of the bit length b of the actual data included in the numerical data string to be encoded. The “identification code that has been optimized so that the total bit length of data is as short as possible” will be defined as “Huffman code”. The simplest example of the optimization processing is “replacement work considering appearance frequency” as exemplified above, but the optimization processing can also be performed by other methods. For example, a plurality of Huffman encoding tables satisfying the above main condition are generated by a predetermined algorithm, and “bits of actual data included in a numerical data string to be encoded are selected from the plurality of tables. In consideration of the application frequency of the length b, the process of selecting the “table with the shortest total bit length of the finally encoded data” is also an aspect of the optimization process.

  Subsequently, the AC component two-dimensional encoding table shown in FIG. 31 is used as a standard encoding table, and the standard encoding table is replaced in consideration of the appearance frequency to create a two-dimensional Huffman encoding table. An example is shown. 39 (a) and 39 (b) show the results of totaling the appearance frequencies of the AC component numerical data in the image data to be compressed in the JPEG format. Here, an example is shown in which a color image is handled by dividing it into a luminance component and a color difference component, and FIG. 39 (a) is a tabulated result for pixels constituting the luminance component, and FIG. 39 (b). Is a total result for the pixels constituting the color difference component.

  In the case of the two-dimensional encoding table, each identification code is determined in association with “a combination of the bit length b and the run length value R”. It is necessary to consider the “appearance frequency of the combination of the length b and the run length value R”. Therefore, the frequency count result shown in FIG. 39 is obtained by determining each run length value and the bit length of the actual data in advance as a stage before performing the encoding using the run length expression of zero. This is obtained as a result of voting using a combination of a length b and a specific run length value R as a voting box.

  The two-dimensional encoding table shown in FIG. 40 is a two-dimensional Huffman encoding obtained by performing replacement work in consideration of the frequency tabulation result shown in FIG. 39 (a) with respect to the standard encoding table shown in FIG. 41, the two-dimensional encoding table shown in FIG. 41 is obtained by performing replacement work in consideration of the frequency tabulation result shown in FIG. 39 (b) with respect to the standard encoding table shown in FIG. It is a dimension Huffman encoding table. In both cases, the standard encoding tables are the same, but are replaced with each other because different frequency count results are considered.

  The Huffman encoding table in FIG. 40 is used when encoding numerical data composed of pixels constituting the luminance component, and the Huffman coding table in FIG. 41 is a code of numerical data composed of pixels constituting the color difference component. It is used when converting. In any figure, the identification code in the column indicated by the double frame is a code that has become shorter than the original identification code by replacement (a code that has obtained a relatively high frequency of appearance), and is indicated by a bold line The identification code in the box indicated by the frame is a code that is longer than the original identification code by replacement (a code that has obtained a result with a relatively low appearance frequency).

  Again, the replacement work is performed only between codes satisfying the condition “two identification codes such that the difference in the corresponding bit length b is an integer multiple of N (N = 4 in this example)”. Also in the Huffman coding tables shown in FIG. 40 and FIG. 41, “when the bit length of the identification code itself is a and the bit length corresponding to the identification code is b, a predetermined reference bit length N (however, N Is an integer greater than or equal to 2), “a + b = k × N” (where k is an arbitrary integer) ”is satisfied.

  In practice, the standard encoding table shown in FIG. 31 is used in common for the luminance component and the color difference component of the color image, and the Huffman encoding table shown in FIG. 40 is used for the luminance component, as shown in FIG. The compression efficiency by the JPEG method was compared with the case where the Huffman coding table was used for the color difference component. As a result, the data capacity of the original image data is assumed to be 100% of the reference, the capacity of the compressed data obtained in the former case is 9.20%, and the capacity of the compressed data obtained in the latter case is 9.13%. A numerical value was obtained. Thus, it can be seen that the compression rate is slightly improved by employing the Huffman coding table.

<<<< §13. Notes on the standard bit length N >>>
Here, the points to be noted regarding the setting of the reference bit length N will be briefly described. In the embodiments described so far, the reference bit length N is set to 4; however, in implementing the present invention, the reference bit length N can be set to an arbitrary integer of 2 or more. (When N = 1 is set, the conventional general encoding method is used).

  However, when the present invention is used commercially, it is preferable to set the reference bit length N to an optimum value in consideration of cost performance. FIG. 42 is a graph showing parameters to be considered when setting the reference bit length N. FIG. 42 (a) is a graph showing the relationship between the reference bit length N and the circuit scale. Generally, the larger the reference bit length N is set, the more the circuit scale can be reduced. On the other hand, FIG. 42B is a graph showing the relationship between the reference bit length N and the compression rate. Generally, the smaller the reference bit length N is set, the higher the compression efficiency (the lower the compression rate).

  Therefore, in order to reduce the circuit scale, it is preferable to set the reference bit length N as large as possible. However, in order to increase the compression efficiency, it is preferable to set the reference bit length N as small as possible. Thus, since the circuit scale and the compression efficiency are in a trade-off relationship, in consideration of this point, it is preferable to set the reference bit length N to an optimal value.

<<<< §14. More practical decryption processing >>>
Finally, a more practical decoding process for implementing the present invention will be described.

<When processing is canceled by each decoding processing unit>
In §4, as shown in FIG. 10, after distributing 16-bit data to each of the eight decoding processing units Q1 to Q8, the decoding processing units Q1 to Q8 are arranged as shown in FIGS. An example of executing the decoding process has been described. In this example, each of the decoding processing units Q1 to Q8 performs processing for extracting numerical data corresponding to actual data from the head of the distributed partial data each time new partial data is distributed. Normal decryption processing will continue as much as possible.

  For example, as shown in FIG. 11, the unit Q1 first decodes the actual data [28] for the first unit code data portion of “01111100”, and then further decodes the second unit code data. Attempt to decrypt the part. However, actually, the decoding of the second unit code data fails, and the result of the decoding process is [28] [ERR] as illustrated. On the other hand, the unit Q4 has successfully decoded two sets of real data [123] [1], and the unit Q7 has three sets of real data [1] [13] [3]. Decryption is successful. On the other hand, the units Q2, Q5, and Q6 fail in normal decoding processing, and cannot retrieve any real data.

  In this way, the number of actual data that each decoding processing unit succeeds in extracting is unknown until the processing is actually executed, but as described in section 4, each decoding processing unit As long as the processing is possible, there is no problem in principle if the processing for extracting the numerical data corresponding to the actual data is continued from the top of the distributed partial data. In the case of the illustrated example, since the maximum bit length of the identification code C posted in the encoding table shown in FIG. 9C is 8, there is no matching identification code even if the first to eighth bits are collated. In this case, normal decryption processing has failed, and the processing should be stopped at that time.

  However, the method described in §4 is not necessarily an efficient method from a practical viewpoint. Specifically, the following two useless points exist in practice. The first waste is that the same actual data is repeatedly extracted by different units. For example, in the example shown in FIG. 12, the actual data [1] extracted by the unit Q4 is also extracted redundantly by the unit Q7. Similarly, the actual data [13] [3] extracted in the unit Q7 is also extracted redundantly in the unit Q8. As described above, even if the same actual data is extracted in duplicate by a plurality of units, only the actual data extracted by the selected unit is finally adopted, so that there is no problem in principle. . However, in practice, it cannot be denied that inefficient processing is performed, such as extra computation time.

  The second waste is a physical wiring problem. In the case of the illustrated example, the actual data extracted from each decoding processing unit is output to the data organization unit as 8-bit numerical data. Therefore, if the number of actual data that can be extracted from one decoding processing unit is n (in the example shown in FIG. 12, n = 4), the M decoding processing units 240 shown in FIG. In the case where information is simultaneously transmitted as a parallel signal to each of the data organization unit 250, only (8 × n) signal lines for transmitting the extracted actual data are required. This becomes a big problem in mounting the circuit.

  Actually, in executing the decoding method according to the present invention, each decoding processing unit does not necessarily have to continue the process for extracting the numerical data corresponding to the actual data "as long as normal decoding processing is possible". Instead, it is sufficient to perform processing for extracting at least one numerical data corresponding to actual data.

  FIG. 43 is a diagram showing another decoding process performed by each of the decoding processing units Q1 to Q8 after distributing 16-bit data to each of the eight decoding processing units Q1 to Q8 as shown in FIG. is there. In the case of this example, each time each of the eight decoding processing units distributes new partial data, numerical data corresponding to actual data for one unit code data from the top of the distributed partial data Process to take out only.

  Specifically, as shown in the figure, when the unit Q1 decodes the actual data [28] for the first unit code data portion "01111100", the unit Q1 stops the processing. Similarly, the units Q3, Q4, Q7, and Q8 also process the real data [251], [123], [1], and [13] for the first unit code data portion, respectively. Cancel. On the other hand, the units Q2, Q5, and Q6 fail normal decoding processing and stop processing.

  In this way, each unit processes the first unit code data portion at the beginning of the distributed partial data, whether it succeeds in normal decoding processing or fails in normal decoding processing. Will be canceled. If it succeeds, the numerical data corresponding to one actual data is extracted, and if it fails, no numerical data is extracted. In short, each unit performs processing for extracting only numerical data corresponding to actual data for one unit code data (the first unit code data at the head of the distributed partial data).

  Also in the example shown in FIG. 43, the information obtained from each unit by normal decoding processing and the normal processing bit length indicating the number of bits involved in the normal decoding processing are transmitted to the data organization unit. The points reported are the same. The values of P1 to P8 shown in the figure indicate the normal processing bit lengths reported from the units Q1 to Q8. FIG. 44 is obtained by adding normal processing end lines Z0 to Z4 to the diagram of the decoding processing process shown in FIG. The normal processing end lines Z0 to Z4 indicate end portions of the bit string on which the normal decoding process has been performed, and the positions thereof are determined based on the normal processing bit lengths P1 to P8 as described in §4. Is done.

  Specifically, first, the unit Q1 is determined as the first adopted unit, and the normal processing end line Z0 is drawn at the head position of the adopted unit Q1. Next, with reference to the normal processing bit length P1 = 8 for the selected unit Q1, the normal processing end line Z1 is drawn at the eighth bit (P1 bit) position from the normal processing end line Z0. Then, another unit Q3 having the normal processing end line Z1 as the head position is determined as a new selection unit, and the normal processing bit length P3 = 16 for the selection unit Q3 is referred to, and the normal processing end line Z1 A normal processing end line Z2 is drawn at the position of the 16th bit (P3th bit). Further, another unit Q7 having the normal processing end line Z2 as the head position is determined as a new adopted unit, and the normal processing bit length P7 = 4 for the selected unit Q7 is referred to and the normal processing end line Z2 is referred to. The normal processing end line Z3 is drawn at the position of the fourth bit (P7 bit). Further, another unit Q8 having the normal processing end line Z3 as the head position is determined as a new selection unit, and the normal processing bit length P8 = 8 for the selection unit Q8 is referred to and the normal processing end line Z3 is referred to. A normal processing end line Z4 is drawn at the position of the 8th bit (P8th bit).

  In this way, the four units Q1, Q3, Q7, and Q8 are the adopted units. FIG. 45 is a diagram showing the normal processing bit portions in the four adopted units Q1, Q3, Q7, and Q8 surrounded by a thick frame. When attention is paid to the normal processing bit portions surrounded by the thick frames, the normal processing end lines Z0 to Z1, the normal processing end lines Z1 to Z2, the normal processing end lines Z2 to Z3, and the normal processing end lines, respectively. It becomes a section of Z3 to Z4, and is a section that is continuous with each other. Therefore, if the numerical data obtained by normal decoding processing by these four adopted units Q1, Q3, Q7, and Q8 are collected, the numerical data string that should be restored can be obtained. That is, as shown in FIG. 45, if the numerical data restored by these adopted units Q1, Q3, Q7, and Q8 are collected and arranged, [28] [251] [1] [13] are obtained.

  The example shown in FIGS. 11 to 13 (an example in which each unit continues processing as long as normal decoding processing is possible) and the example shown in FIGS. 43 to 45 (each unit corresponds to one actual data) Comparing with the example in which only the data is extracted, it can be seen that the two wastes included in the former are omitted in the latter. That is, in the latter case, the same actual data is not duplicated by different units, and numerical data corresponding to one actual data (in the illustrated example, 8 bits) is not obtained. It is sufficient to provide wiring for outputting only the numerical data) to the data organization unit.

  However, the former is superior to the latter. Comparing FIG. 13 with FIG. 45, in the former, decoding is performed for the portions of blocks B1 to B10 in the encoded data sequence shown in the upper stage by the first parallel processing, and [28] [251] ] [1] [13] [3] are decoded for the five sets of numerical data, whereas in the latter case, the blocks B1 to B9 are decoded by the first parallel processing. Only four sets of numerical data [28] [251] [1] [13] are decoded. That is, in the latter case, the decoding of the block B10 is not performed in the first parallel processing, but is sent to the second parallel processing. This is because in the latter case, the unit Q8 takes the bit string “0011” of the block B10 as the numerical data, because “each unit stops processing when the numerical data corresponding to one actual data is extracted”. This is because the processing is stopped when the numerical data [13] is taken out although it can be taken out as [3].

  In order to correct such an adverse effect, a compromise method that adopts both the former and the latter may be employed. In other words, in general terms using M decoding processing units, for each of the first to (M−1) th units, “every time new partial data is distributed, A process for extracting only numerical data corresponding to actual data for one unit code data from the beginning of the distributed partial data (the former process) ”is performed. Every time partial data is distributed, the process for extracting numerical data corresponding to the actual data from the beginning of the distributed partial data is continued as long as normal decoding processing is possible (the latter process). You can do it.

  In this compromise method, in the example of FIG. 45 (M = 8 example), only the numerical data corresponding to one actual data is shown for the first to seventh units Q1 to Q7 as shown in the figure. As for the eighth unit Q8, the process of extracting the actual data is continued as long as the normal decoding process is possible. Therefore, [3] is extracted following [13]. In this case, the position of the normal processing end line Z4 moves to the right by 4 bits and becomes the right end of the block B10. Thus, similarly to the example shown in FIG. 13, five sets of numeric data [28] [251] [1] [13] [3] are decoded by the first parallel processing. In this case, since there is a possibility that a plurality of sets of numerical data may be output from the eighth unit Q8, it is necessary to prepare wiring corresponding to this, but the first to seventh units For the units Q1 to Q7, it is sufficient to prepare wiring necessary for one numerical data.

  In this way, at the decoding processing stage according to the present invention, each time new partial data is distributed, the M decoding processing units correspond to an arbitrary number of actual data from the beginning of the distributed partial data. It is only necessary to perform processing for extracting the numerical data to be performed, and it is possible to arbitrarily set the time point at which the individual decoding processing unit is stopped. In addition, the examples shown in FIGS. 43 to 45 are examples using a one-dimensional encoding table. However, in the example using the two-dimensional encoding table described in §9, the processing by individual decoding processing units is also performed. The stop point can be set arbitrarily. For example, in the case of the example shown in FIG. 35, if each unit stops the process at the time of performing the decoding process on the first unit code data portion at the head of the distributed partial data, The adopted units marked with “◎” are Q1 (P1 = 8), Q3 (P3 = 16), and Q7 (P7 = 12), and the decoding from the top to the 36th bit is performed in the first parallel processing. Complete.

  That is, when decoding the encoded data using the two-dimensional encoding table, the M decoding processing units start from the top of the distributed partial data every time new partial data is distributed. The process for extracting the numerical data corresponding to the run length value and the actual data may be repeated an arbitrary number of times. Specifically, the normal decoding process may be continued as many times as possible, or when the run-length value for one unit code data and the numerical data corresponding to the actual data are extracted. Processing may be stopped. Of course, as a compromise method, for the first to (M−1) th units, the processing is performed when the run length value for one unit code data and the numerical data corresponding to the actual data are extracted. For the Mth unit, the processing may be continued as long as normal decoding processing is possible.

<Responsible for restoration processing based on run length value>
In the method using the two-dimensional encoding table described in §9, numerical data indicating 0 is obtained from each distributed partial data while referring to the two-dimensional encoding table by parallel processing by M decoding processing units. The decoding process is performed to extract the run-length value indicating the number of times the data is enumerated and the numerical data corresponding to the actual data following the numerical data indicating 0, and each is collected by one or more parallel processes. A decoded data string is generated by arranging numerical data based on the information.

  In the flowchart shown in FIG. 17, the decoding process stage shown as step S24 is a parallel process executed by M decoding process units, and the data organization stage shown as step S25 is a decoding process. This is a process for generating a data string. In the method described in §10, in the decoding process step in step S24, the numerical data indicating 0 is arranged for the number of times corresponding to the run-length value, and then the numerical data corresponding to the actual data is arranged, whereby the original data sequence is changed. The decoding process to restore is performed, and in the subsequent data organization stage of step S25, the result of the decoding process by the M decoding processing units is selected, and the numerical data indicating 0 and the numerical data corresponding to each actual data are obtained. A process of generating the arranged decoded data string was performed.

  In other words, in the method described in §10, in the decoding processing stage of step S24, each of the M decoding processing units enumerates the numerical data indicating 0 for the number of times corresponding to the run length value, and then the actual data. The process of restoring the original data is performed by arranging the numerical data corresponding to the above, and the data organization unit generates the decoded data sequence by arranging the restored data in the data organization stage of step S25 Had gone. In other words, in this method, each of the M decoding processing units is in charge of the process of restoring the enumerated data of 0 based on the run length value.

  However, in practice, it is preferable that the data organization unit performs the restoration process based on the run length value. The reason is to make the wiring from each decoding processing unit to the data organization unit more efficient. As shown in FIG. 19, an actual decoding device requires wiring for transmitting information indicating processing results from each of the M decoding processing units 240 to the data organization unit 250. The data organization unit 250 can receive the information obtained as a result of one parallel processing by the M decoding processing units 240 in a time-sharing manner, but practically receives it as a parallel signal at the same timing, It is preferable to perform a process of generating a decrypted data string. Then, if the decoding processing units 240 on the M decoding processing units 240 side have already performed restoration processing based on the run length value (processing that lists the numerical data indicating 0 as many times as the run length value), these In order to transmit this numerical data as a parallel signal to the data organization unit 250, an enormous number of wires are required.

  Therefore, in practice, in the decoding processing stage, each of the M decoding processing units 240 executes a process of outputting the extracted run-length value and numerical data corresponding to the actual data as they are, and in the data organization stage. The data organization unit 250 executes the process of restoring the original data by arranging the numeric data corresponding to the actual data after arranging the numeric data indicating 0 for the number of times corresponding to the run-length value. A process of generating a decoded data string is performed by arranging the data. Then, wiring for transmitting the run length value, the numerical data corresponding to the actual data, and the normal processing bit length should be prepared from each decoding processing unit 240 to the data organization unit 250. Therefore, the number of wirings can be saved greatly.

<Decryption using dedicated reference table>
The encoding table used in the encoding method according to the present invention is “a portion of a bit from the beginning when the bit length of the identification code of interest is a, regardless of any identification code in the table. Is a table that satisfies the condition that there is no other identification code in the table that is the same as the target identification code. Then, when performing the decoding, by utilizing such a condition, the 1 bit, 2 bit, 3 bit,... It is possible to perform processing for determining whether there is a matching identification code.

  As described above, the basic principle of decoding is the matching determination process with the identification code in the encoding table. However, in practice, the following efficient matching determination process is performed. This processing is a well-known technique used for decoding JPEG images and the like, but a specific example when applied to the present invention will be briefly described below.

  In order to perform the efficient match determination process described here, it is necessary to prepare a dedicated decoding reference table in advance based on an encoding table used for decoding. Here, FIG. 46 and FIG. 47 illustrate the decoding reference tables created based on the “AC component coding table” shown in FIG.

  The decoding first reference table shown in FIG. 46 includes the bit length a of the identification code itself, the number of code words w indicating the total number of identification codes having the bit length a (the total number in the table of FIG. 31), and the bit. Among the identification codes having the length a, the identification code Cmin having the smallest value is accommodated. For example, the first row of the reference table contains data of a = 3, w = 1, and Cmin = “000”. This is because the bit length is “3” in the table shown in FIG. ”Means that there is only one identification code (b = 1, R = 0), and the identification code is“ 000 ”. Similarly, the data of a = 4, w = 4, Cmin = “0010” is accommodated in the second row of this reference table. This is because the bit length is “0” in the table shown in FIG. 4 ”(b = 0, R = 0 column, b = 0, R = 15 column, b = 4, R = 0 column, b = 4, R = 1 column) ), The minimum value of these four identification codes is “0010”. The same applies hereinafter.

  On the other hand, the second reference table for decoding shown in FIG. 47 identifies each identification code accommodated in the table in FIG. 31 for the identification codes having the same bit length a in ascending order of the bit length a. It is a table in which the values of b and R indicating the accommodation position of the identification code are listed in order from the smallest code. For example, in the first row of the reference table, the accommodation position “b = 1, R = 0” of the identification code “000” is described, and in the second line, the accommodation position “b =” of the identification code “0010”. 0, R = 0 (= EOB) ”is described, the accommodation position“ b = 4, R = 0 ”of the identification code“ 0011 ”is described in the third line, and the identification code“ 0011 ”is described in the fourth line. 0100 ”is described as“ b = 4, R = 1 ”. Since it is not necessary to describe the identification code itself in the second reference table for decoding, the identification code is shown in parentheses outside the right column in the figure for reference. In addition, the head address of each bit length a is indicated by an arrow outside the left column.

  These two reference tables show substantially the same contents as the table of FIG. 31, and if these two tables are created in advance, decoding is performed in an efficient manner as described below. It is possible. Here, a case will be described as an example in which decoding is performed on 24-bit data distributed to the decoding processing unit Q3 shown in FIG. As shown in FIG. 35, for the decoding processing unit Q3, the first 10-bit data “1111011000” matches the accommodation position “b = 6, R = 3” in the table of FIG.

  FIG. 48 is a diagram showing the principle of an efficient decoding process using the first and second reference tables for decoding. First, in order to make a match determination for an identification code having a bit length a = 3, the identification code Cmin “000” (bits) described in the row of the bit length a = 3 is obtained from the first reference table shown in FIG. The minimum value of the identification code having the length 3 is taken out and subtracted by aligning it with the head of the bit string in the unit Q3 to obtain the difference d. In FIG. 48, circled numeral 3 shows such subtraction. As shown in the figure, since the first three bits of the bit string in the unit Q3 are “111”, the subtraction performed here is “111−000 = 111”, and the difference d = “111” is obtained.

  Subsequently, the number of code words w (in this case, w = 1) described in the row with the bit length a = 3 is extracted from the first reference table shown in FIG. 46, and “0 ≦ d <w” is satisfied? Check for no. Since the decimal notation of the difference d = “111” is d = 7, d ≧ w, and when a = 3, “0 ≦ d <w” is not satisfied. Such processing is repeatedly executed while increasing “a” by 1 until “0 ≦ d <w” is satisfied.

  For example, when a = 4, the identification code Cmin “0010” (the minimum value of the identification code having a bit length of 4) is taken out, and as shown in the circled number 4 in FIG. 48, the bit string in the unit Q3 Is subtracted from the first 4 bits “1111”, and “1111-0010 = 1110” is obtained, and a difference d = “1101 (13 in decimal notation)” is obtained. On the other hand, since the number of codewords w written in the row of bit length a = 4 is w = 4, d ≧ w, and even when a = 4, “0 ≦ d <w” is not satisfied. .

  Subsequently, when a = 5, the identification code Cmin “01100” (the minimum value of the identification code having a bit length of 5) is taken out, and as shown by the circled number 5 in FIG. 48, the bit string in the unit Q3 Is subtracted from the first five bits “11110”, and the difference d = “10010 (18 in decimal notation)” is obtained as “11110-01100 = 1010”. On the other hand, the number of codewords w written in the row with the bit length a = 5 is w = 5, so d ≧ w, and even when a = 5, “0 ≦ d <w” is not satisfied. . Similarly, in the case of a = 6 to 9, “0 ≦ d <w” is not satisfied with respect to the difference d obtained by subtraction.

  Next, in the case of a = 10, the identification code Cmin “1111010110” (the minimum value of the identification code having a bit length of 10) is taken out, and as indicated by the circled number 10 in FIG. Subtraction is performed on the first 10 bits “1111011000” of the bit string, and the difference d = “0000000010 (2 in decimal notation)” is obtained as “1111011000-1111010110 = 0000000010”. On the other hand, since the number of codewords w written in the row with the bit length a = 10 is w = 20, “0 ≦ d <w” is satisfied for the first time when a = 10.

  Thus, when “0 ≦ d <w” is satisfied, the second reference table shown in FIG. 47 is referred to, and the d-th data is extracted from the start address of the bit length a at that time. In the case of the above example, the second data, that is, “b = 6, R = 3” is extracted from the head address of the bit length a = 10. The data “b = 6, R = 3” thus extracted is exactly the bit length b and the run length value R indicated by the identification code that matches the first 10 bits of data “1111011000” of the decoding processing unit Q3. .

  If the decoding method described above is employed, a very efficient match determination process can be performed as compared with the method of comparing each column of the table of FIG. Note that when this decoding method is adopted, the data output unit 170 in the encoding device shown in FIG. 18 is illustrated on the basis of the encoding table T (two-dimensional encoding table) stored in the table storage unit 120. The first reference table for decoding as shown in FIG. 46 and the second reference table for decoding as shown in FIG. 47 are provided, and these reference tables themselves are stored in the encoded data file F, or What is necessary is just to incorporate the table specific information which specifies these reference tables. As described above, the reference table shown in FIGS. 46 and 47 is a table that performs the same function as the table of FIG. 31 and is a table that shows substantially the same contents.

  Note that in order to speed up the above-described decoding calculation processing, individual subtraction processing (specifically, as shown in the first reference table of FIG. 46) as shown by the circled numbers 3 to 10 in FIG. The process of parallelly subtracting the identification code Cmin for the bit length a = 3 to the identification code Cmin for the bit length a = 14 by aligning them with the head of the 24-bit data distributed to the unit Q3) And do it. That is, if a plurality of hardware units for executing individual subtraction processes are prepared in the decoding processing unit Q3, subtraction for the bit length a = 3, subtraction for the bit length a = 4, bit length Instead of repeatedly performing the subtraction for a = 5,... and each subtraction process in turn, all the subtraction processes can be performed in parallel, and the subtraction results for bit length a = 3 to 14 can be performed simultaneously. Can be obtained.

110: Data storage unit 120: Table storage unit 130: Data extraction unit 140: Actual data generation unit 150: Identification code selection unit 160: Unit code data generation unit 170: Data output unit 180: Frequency counting unit 190: Table correction unit 210 : Data storage unit 220: Table storage unit 230: Data distribution unit 240 (1), 240 (2),..., 240 (m): Decoding processing unit 250: Data organization unit 260: Data output unit 300: JPEG image Compression processing apparatus 310: DCT means 320: quantization means 330: encoding means 400: JPEG image decompression processing apparatus 410: decoding means 420: inverse quantization means 430: inverse DCT means a: bit of identification code C itself Length B1 to B11: Data block b having reference bit length N: Bit length C, C1, C2, C3, C of actual data D , C5,...: Identification code C00 to C88: Identification code Cmin: Minimum identification code D, D1, D2, D3, D4, D5,...: Numerical data / actual data d: Difference E: Numerical data string F: Encoded data file F1: Header part F2: Body part F3: Footer part G: Decoded data string H: Table specifying information i: Decoding processing unit number J: Count value k: Arbitrary integer (1, 2, 3,4, ...)
L: Number of bits that can be processed by the decoding processing unit (integer multiple of N)
M: Number of decoding processing units N: Reference bit length (integer of 2 or more)
P1 to P8: Normal processing bit lengths Q1 to Q8: Decoding processing unit R: Run length value Rmax: Maximum run length value S: Encoded data sequence S11 to S27: Steps T, T1, T2, T3 of the flowchart T4: Encoding table U, U1, U2, U3, U4, U5,... Un: Unit code data Umax: Maximum bit length of unit code data w: Number of codewords X: Data of 8 × 8 pixel block Y: Compression Data Z0 to Z4: Normal processing end line

Claims (39)

An encoding method for encoding a numeric data string composed of fixed-length bits using a variable-length bit string,
Arithmetic processing unit
A data input stage for inputting a numeric data string to be encoded;
A table input stage for inputting a coding table indicating a unique identification code corresponding to each bit length;
A data extraction stage for sequentially extracting individual numerical data from the input numerical data string;
An actual data generation stage for generating actual data by deleting redundant bits from the extracted numerical data;
An identification code selection step of selecting an identification code corresponding to the bit length of the generated actual data with reference to the encoding table;
A unit code data generation step for generating unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
Repeatedly executing the data extraction step, the actual data generation step, the identification code selection step, and the unit code data generation step for each of the numerical data constituting the input numerical data string;
A data output stage for arranging the generated unit code data in order and outputting them as an encoded data string;
Run
The encoding table is
It is a table showing the correspondence between individual bit lengths and unique identification codes corresponding to the bit lengths for a plurality of bit lengths within a predetermined range sufficient to represent the actual data,
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code The code does not exist in this table, and when the bit length corresponding to the identification code of interest is b, “a + b = k × N ”(where k is an arbitrary integer).
In the actual data generation stage, as actual data indicating the extracted numerical data, when the numerical data is data indicating 0, a virtual bit string having a bit length of 0 is data indicating a positive value Is a variable-length bit string that does not include 0 at the beginning, and a variable-length bit string that does not include 1 at the beginning if the data indicates a negative value. Method. An encoding method for encoding a numeric data string composed of fixed-length bits using a variable-length bit string,
Arithmetic processing unit
A data input stage for inputting a numeric data string to be encoded;
A table input stage for inputting a two-dimensional encoding table indicating a unique identification code corresponding to a combination of individual bit lengths and individual run length values;
A data extraction stage for sequentially extracting individual numerical data from the input numerical data string;
When the extracted numerical data is data indicating 0 and the count value so far has not reached the maximum value Rmax, the number of times the numerical data indicating 0 is continuously extracted is counted as a run length value. A run length value counting stage;
When the extracted numerical data is data indicating a positive value, a variable-length bit string that does not include a leading zero is generated as actual data indicating the numerical data, and the extracted numerical data is data indicating a negative value In some cases, a variable-length bit string not including 1 at the beginning is generated as actual data indicating the numerical data, the extracted numerical data is data indicating 0, and the count value reaches the maximum value Rmax. If so, a real data generation stage for generating a virtual bit string having a bit length of 0 as real data;
With reference to the two-dimensional encoding table, an identification code corresponding to a combination of a bit length of the generated actual data and a run length value when the actual data is generated is selected, and the count value An identification code selection stage for resetting to zero,
A unit code data generation step for generating unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
The data extraction step is repeatedly executed for each of the numerical data constituting the input numerical data string, and the run length value counting step, the actual data generation step, the identification code selection step, and the unit code data generation step are performed. , Repeat as needed, and
A data output stage for arranging the generated unit code data in order and outputting them as an encoded data string;
Run
When the predetermined maximum run length value determined in advance is Rmax, the encoding table has a plurality of bit lengths within a predetermined range sufficient to represent the actual data, and a range up to Rmax. For each combination of multiple run length values, a table showing the correspondence between each combination and a unique identification code corresponding to the combination,
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. The code does not exist in this table, and when the bit length corresponding to the target identification code is b, “a + b = N” is a predetermined reference bit length N (where N is an integer of 2 or more). A numerical data string encoding method, characterized in that the table satisfies a condition of “k × N” (where k is an arbitrary integer). The encoding method according to claim 2 , wherein
In the data extraction stage, when extracting numeric data, it is checked whether or not “zero persistent state that all numeric data subsequent to the end of the numeric data string including the numeric data to be extracted is 0”. When the investigation process is executed and it is confirmed by the investigation process that the zero permanent state is present,
In the actual data generation stage, a virtual bit string having a bit length of 0 is generated as actual data, and in the identification code selection stage, a termination code indicating a zero permanent state is selected as an identification code. Encoding method. An encoding method for encoding a numeric data string composed of fixed-length bits using a variable-length bit string,
The arithmetic processing unit generates actual data representing specific numerical data using a variable-length bit string, and adds an identification code having at least information indicating the bit length of the actual data to the head of the actual data. By doing this, generate unit code data having information indicating at least the specific numerical data itself, execute a process of arranging the generated plurality of unit code data in order and outputting them as an encoded data string,
When selecting an identification code to be added, an encoding table indicating at least “a correspondence relationship between a plurality of bit lengths within a predetermined range and an identification code corresponding to the bit length” is used, and the table However, when focusing on any identification code in the table, when the bit length of the target identification code itself is a, the a-bit portion from the beginning is the same as the target identification code. No identification code exists in this table, and when a bit length corresponding to the identification code of interest is b, “N” is an integer greater than or equal to 2 a + b = k × N ”(where k is an arbitrary integer).
As the appearance frequency of the bit length b of actual data or the appearance frequency of the combination of the bit length b and the run length value R is higher, an encoding table in which an identification code having a shorter bit length a is associated is used. A numerical data string encoding method characterized by the above. The encoding method according to claim 4 , wherein
A frequency counting stage for counting the appearance frequency of the bit length b of the actual data or the appearance frequency of the combination of the bit length b and the run length value R for the numerical data string to be encoded;
The frequency of occurrence of the bit length b of the actual data or the bit by performing the process of exchanging the contents of the table for the bit lengths b having an integer multiple difference of the reference bit length N in the existing standard encoding table A table modification stage for generating a modified encoding table in which an identification code having a shorter bit length a is associated with an increase in the appearance frequency of the combination of the length b and the run length value R;
And execute
A numerical data string encoding method, wherein an identification code is selected by referring to the corrected encoding table in an identification code selection step. In the encoding method in any one of Claims 1-5 ,
An encoding method for a numerical data string, wherein a data file including an encoded data string and an encoding table used for encoding processing is output in a data output stage. In the encoding method in any one of Claims 1-5 ,
An encoding method of a numerical data string, wherein a data file including an encoded data string and table specifying information for specifying an encoding table used for encoding processing is output in a data output stage. A decoding method for restoring a numeric data sequence that is a target of encoding with respect to an encoded data sequence encoded by the encoding method of the numeric data sequence according to claim 2 ,
An arithmetic processing device including a plurality of M decoding processing units is provided.
A data input stage for inputting an encoded data sequence to be decoded;
A table input stage for inputting a two-dimensional encoding table used for encoding;
Decoding of a plurality of M units each having a function of performing decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax when the maximum bit length of unit code data is Umax) A data distribution step of distributing a part of the encoded data sequence as partial data to a processing unit;
By means of parallel processing by the M decoding processing units, referring to the two-dimensional encoding table, a run length value indicating the number of times numeric data indicating 0 is enumerated from each distributed partial data, A decoding process stage for performing a decoding process to extract numerical data corresponding to actual data following the numerical data shown;
A data organization stage for selecting a result of the decoding processing by the M decoding processing units and generating a decoded data string in which numerical data indicating 0 and numerical data corresponding to individual actual data are arranged;
A data output step of outputting the generated decoded data sequence;
Run
In the data distribution stage, from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the head of the undecoded portion of the encoded data string. The process of distributing the bit string to the i-th unit (i = 1 to M) is repeated until decoding of all parts of the encoded data string is completed,
In the decoding process step, each time the M decoding processing units distribute new partial data, numerical data corresponding to the run length value and the actual data is obtained from the head of the distributed partial data. Do the processing to take out,
In the data organization stage, when processing results are obtained from the M decoding processing units by one parallel processing, the first unit is first determined as the first adopted unit, and normal decoding is performed by this adopted unit. Recognize the last bit that has been processed, and continue as much as possible the process of deciding another unit to which the partial data with the bit immediately after the last bit as the first bit is distributed as the new adopted unit Collecting numerical data that has been successfully decoded in each selected unit, and generating a decoded data string by arranging the numerical data based on the information collected by one or more parallel processes. A method of decoding a numerical data string characterized by “At least an identification code indicating a predetermined bit length followed by actual data consisting of a bit string having the bit length, the total length of which is a predetermined reference bit length N (where N is an integer of 2 or more ) Is a decoding method for restoring at least numerical data corresponding to individual actual data for an encoded data string configured by arranging a plurality of sets of unit code data set to be an integral multiple of ,
Dividing the encoded data sequence in units of an integer multiple of N bits to generate a plurality of partial data, and distributing each partial data to a plurality of M decoding processing units;
Performing a decoding process on the distributed partial data by parallel processing of the plurality of M decoding processing units;
Generate a decoded data string by arranging numerical data that has been successfully decoded,
“Subsequent to an identification code indicating a combination of a predetermined bit length and a predetermined run length value, it has a structure in which real data including a bit string having the bit length is arranged, and numerical data indicating 0 is expressed as the run length. A data string in which numerical data corresponding to the actual data is arranged after being enumerated a number of times corresponding to the value, and the total length is an integral multiple of a predetermined reference bit length N (where N is an integer of 2 or more). In order to restore an original data sequence in which numerical data indicating 0 and individual actual data are arranged for an encoded data sequence configured by arranging a plurality of sets of set unit code data (maximum bit length Umax) In addition,
An arithmetic processing device including a plurality of M decoding processing units is provided.
A data input stage for inputting an encoded data sequence to be decoded;
A table input stage for inputting a two-dimensional encoding table indicating a combination of a specific bit length corresponding to each identification code and a specific run length value;
Part of the encoded data string for a plurality of M decoding processing units each having a function of performing decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax). A data distribution stage for distributing the data as partial data;
By means of parallel processing by the M decoding processing units, referring to the two-dimensional encoding table, a run length value indicating the number of times numeric data indicating 0 is enumerated from each distributed partial data, A decoding process stage for performing a decoding process to extract numerical data corresponding to actual data following the numerical data shown;
A data organization stage for selecting a result of the decoding processing by the M decoding processing units and generating a decoded data string in which numerical data indicating 0 and numerical data corresponding to individual actual data are arranged;
A data output step of outputting the generated decoded data sequence;
Run
In the data distribution stage, from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the head of the undecoded portion of the encoded data string. The process of distributing the bit string to the i-th unit (i = 1 to M) is repeated until decoding of all parts of the encoded data string is completed,
In the decoding process step, each time the M decoding processing units distribute new partial data, numerical data corresponding to the run length value and the actual data is obtained from the head of the distributed partial data. Do the processing to take out,
In the data organization stage, when processing results are obtained from the M decoding processing units by one parallel processing, the first unit is first determined as the first adopted unit, and normal decoding is performed by this adopted unit. Recognize the last bit that has been processed, and continue as much as possible the process of deciding another unit to which the partial data with the bit immediately after the last bit as the first bit is distributed as the new adopted unit Collecting numerical data that has been successfully decoded in each selected unit, and generating a decoded data string by arranging the numerical data based on the information collected by one or more parallel processes. A method of decoding a numerical data string characterized by The decoding method according to claim 9 , wherein
In the decoding process stage, each of the M decoding processing units extracts numerical data corresponding to the run-length value and the actual data from the head of the distributed partial data each time new partial data is distributed. The numerical data string decoding method is characterized by continuing normal decoding processing as much as possible. The decoding method according to claim 9 , wherein
In the decoding process stage, each time the M decoding processing units distribute new partial data, the run length value and actual data for one unit code data are converted from the head of the distributed partial data. A method for decoding a numeric data string, wherein a process for extracting only corresponding numeric data is performed. The decoding method according to claim 9 , wherein
In the decoding process stage, each of the first to (M−1) -th units among the M decoding processing units is distributed each time new partial data is distributed. Each time the M-th unit distributes new partial data, it performs a process for extracting only the run-length value for one unit code data and the numerical data corresponding to the actual data. A method for decoding a numerical data string, characterized in that normal decoding processing is continued as much as possible for processing for extracting numerical data corresponding to run length values and actual data from the beginning of the distributed partial data . In the decoding method in any one of Claims 9-12 ,
In the decoding process stage, each of the M decoding processing units restores the original data by arranging the numerical data corresponding to the actual data after arranging the numerical data indicating 0 as many times as the run-length value. Execute the process,
A decoding method of a numerical data string, wherein a decoded data string is generated by arranging restored data in a data organization stage. In the decoding method in any one of Claims 9-12 ,
In the decoding process stage, each of the M decoding processing units executes a process of outputting the run length value and the numerical data corresponding to the actual data as they are,
In the data organization stage, based on the information collected from each adopted unit, the original data is restored by arranging the numerical data indicating 0 for the number of times corresponding to the run-length value and arranging the numerical data corresponding to the actual data. A decoding method for a numerical data string, wherein the decoding data string is generated by arranging the restored data by performing a process to perform In the decoding method in any one of Claims 9-14 ,
When a data file including an encoded data string and an encoding table used for encoding processing is given,
In the data input stage, a process of extracting an encoded data string from the data file is performed,
A numerical data string decoding method, comprising: performing a process of extracting an encoding table from the data file in a table input stage. In the decoding method in any one of Claims 9-14 ,
When a data file including an encoded data string and table specifying information for specifying an encoding table used for encoding processing is given,
In the data input stage, a process of extracting an encoded data string from the data file is performed,
A method of decoding a numerical data string, wherein, in a table input stage, after performing processing for extracting table specifying information from the data file, a table specified by the table specifying information is selected and used. The decoding method according to any one of claims 9 to 16 ,
In the data distribution stage, partial data is distributed to a plurality of M decoding processing units such that M ≧ 1 + L / N,
A decoding method for a numerical data string, wherein parallel processing is performed by these M decoding processing units in a decoding processing stage. An encoding device that encodes a numeric data string composed of fixed-length bits using a variable-length bit string,
A data storage unit for inputting and storing a numeric data sequence to be encoded;
A table storage unit for storing a coding table indicating a unique identification code corresponding to each bit length;
A data extraction unit for sequentially extracting individual numerical data from the numerical data string stored in the data storage unit;
An actual data generation unit that generates actual data by deleting redundant bits from the extracted numerical data;
An identification code selection unit that selects an identification code corresponding to the bit length of the generated actual data with reference to the encoding table;
A unit code data generating unit that generates unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
A data output unit that arranges the generated unit code data in order and outputs the encoded data as an encoded data sequence;
With
The encoding table is
It is a table showing the correspondence between individual bit lengths and unique identification codes corresponding to the bit lengths for a plurality of bit lengths within a predetermined range sufficient to represent the actual data,
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code The code does not exist in this table, and when the bit length corresponding to the identification code of interest is b, “a + b = k × N ”(where k is an arbitrary integer).
In the case where the actual data generation unit is a data indicating a positive value as a virtual bit string having a bit length of 0 when the numerical data is data indicating 0 as the actual data indicating the extracted numerical data Is a variable-length bit string that does not include 0 at the beginning, and a variable-length bit string that does not include 1 at the beginning if the data indicates a negative value. Device. An encoding device that encodes a numeric data string composed of fixed-length bits using a variable-length bit string,
A data storage unit for inputting and storing a numeric data sequence to be encoded;
A table storage unit for storing a two-dimensional encoding table indicating a unique identification code corresponding to a combination of individual bit lengths and individual run length values;
A data extraction unit for sequentially extracting individual numerical data from the numerical data string stored in the data storage unit;
When the extracted numerical data is data indicating 0 and the count value so far has not reached the maximum value Rmax, the number of times the numerical data indicating 0 is continuously extracted is counted as a run length value. If the extracted numerical data is data indicating a positive value, a process of generating a variable-length bit string that does not include a leading zero as actual data indicating the numerical data is performed. When the data is a data indicating a negative value, a process of generating a variable-length bit string not including 1 at the head is performed as actual data indicating the numerical data, and the extracted numerical data is data indicating 0 And when the count value has reached the maximum value Rmax, an actual data generation unit that generates a virtual bit string having a bit length of 0 as actual data;
With reference to the two-dimensional encoding table, an identification code corresponding to a combination of a bit length of the generated actual data and a run length value when the actual data is generated is selected, and the count value An identification code selection unit for resetting to 0,
A unit code data generating unit that generates unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
A data output unit that arranges the generated unit code data in order and outputs the encoded data as an encoded data sequence;
With
When the predetermined maximum run length value determined in advance is Rmax, the encoding table has a plurality of bit lengths within a predetermined range sufficient to represent the actual data, and a range up to Rmax. For each combination of multiple run length values, a table showing the correspondence between each combination and a unique identification code corresponding to the combination,
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code. The code does not exist in this table, and when the bit length corresponding to the target identification code is b, “a + b = N” is a predetermined reference bit length N (where N is an integer of 2 or more) An apparatus for encoding a numerical data string, characterized in that the table satisfies a condition “k × N” (where k is an arbitrary integer). The encoding device according to claim 19 ,
When the data extraction unit extracts the numerical data, it checks whether or not “a zero-permanent state in which all the numerical data subsequent to the end of the numerical data string including the numerical data to be extracted is 0” is in effect. Run the investigation process,
When the real data generation unit is confirmed to be in the zero permanent state by the investigation process, a virtual bit string having a bit length of 0 is generated as real data,
A numerical data string encoding apparatus, wherein an identification code selection unit selects, as an identification code, an end code indicating a zero permanent state when it is confirmed that the zero permanent state is obtained by the examination process. An encoding device that encodes a numeric data string composed of fixed-length bits using a variable-length bit string,
A data storage unit for inputting and storing a numeric data sequence to be encoded;
A table storage unit for storing a coding table indicating a unique identification code corresponding to each bit length;
A data extraction unit for sequentially extracting individual numerical data from the numerical data string stored in the data storage unit;
An actual data generation unit that generates actual data by deleting redundant bits from the extracted numerical data;
An identification code selection unit that selects an identification code corresponding to the bit length of the generated actual data with reference to the encoding table;
A unit code data generating unit that generates unit code data indicating the extracted numerical data by adding the selected identification code to the head of the generated actual data;
A data output unit that arranges the generated unit code data in order and outputs the encoded data as an encoded data sequence;
With
The encoding table is
It is a table showing the correspondence between individual bit lengths and unique identification codes corresponding to the bit lengths for a plurality of bit lengths within a predetermined range sufficient to represent the actual data,
When any of the identification codes in this table is focused, another identification is made such that when the bit length of the focused identification code itself is a, the a-bit portion from the beginning is the same as the focused identification code The code does not exist in this table, and when the bit length corresponding to the identification code of interest is b, “a + b = k × N ”(where k is an arbitrary integer).
The encoding table stored in the table storage unit has a shorter bit length a as the appearance frequency of the bit length b of the actual data or the appearance frequency of the combination of the bit length b and the run length value R increases. An encoding device for a numerical data string, wherein the encoding table is associated with an identification code. The encoding device according to any one of claims 18 to 20 ,
The encoding table stored in the table storage unit has a shorter bit length a as the appearance frequency of the bit length b of the actual data or the appearance frequency of the combination of the bit length b and the run length value R increases. An encoding device for a numerical data string, wherein the encoding table is associated with an identification code. The encoding device according to claim 21 or 22 ,
A frequency counting unit that counts the appearance frequency of the bit length b of the actual data or the appearance frequency of the combination of the bit length b and the run length value R for the numerical data string stored in the data storage unit;
The frequency of occurrence of the bit length b of the actual data or the bit by performing the process of exchanging the contents of the table for the bit lengths b having an integer multiple difference of the reference bit length N in the existing standard encoding table A table for generating a modified encoding table in which an identification code having a shorter bit length a is associated with each other as the appearance frequency of the combination of the length b and the run length value R is higher, and storing the table in the table storage unit Correction part,
A numerical data string encoding device characterized by further comprising: The encoding device according to any one of claims 18 to 23 ,
A data output unit outputs an encoding table stored in a table storage unit or table specifying information for specifying the encoding table together with an encoded data sequence. “Subsequent to an identification code indicating a combination of a predetermined bit length and a predetermined run length value, it has a structure in which real data including a bit string having the bit length is arranged, and numerical data indicating 0 is expressed as the run length. A data string in which numerical data corresponding to the actual data is arranged after being enumerated a number of times corresponding to the value, and the total length is an integral multiple of a predetermined reference bit length N (where N is an integer of 2 or more). Decoding that restores an original data sequence in which numerical data indicating 0 and individual actual data are arranged for an encoded data sequence configured by arranging a plurality of sets of set unit code data (maximum bit length Umax) Device.
A data storage unit for inputting and storing an encoded data sequence to be decoded;
A table storage unit for storing a two-dimensional encoding table indicating a combination of a specific bit length corresponding to each identification code and a specific run length value;
A plurality of M decoding processing units that perform decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax) in parallel,
A data distribution unit that distributes a part of the encoded data sequence stored in the data storage unit as partial data to the M decoding processing units;
A data organization unit that selects a result of the decoding processing by the M decoding processing units, and generates a decoded data string in which numerical data indicating 0 and numerical data corresponding to individual real data are arranged;
A data output unit for outputting the generated decoded data sequence;
With
The data distribution unit counts from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the beginning of the undecoded portion of the encoded data string. The process of distributing the bit string to the i-th unit (i = 1 to M) is repeated until decoding of all parts of the encoded data string is completed,
The M decoding processing units refer to the two-dimensional encoding table, run length values indicating the number of times numerical data indicating 0 is listed from the distributed partial data, and numerical data indicating 0 And a decoding process for extracting the numerical data corresponding to the actual data that follows, and every time new partial data is distributed, the run length value and the actual data from the beginning of the distributed partial data Process to extract the numerical data corresponding to
When the processing result is obtained from the M decoding processing units by one parallel processing, the data organization unit first determines the first unit as the first selected unit, and the selected unit performs normal decoding. Recognize the last bit that has been processed, and continue as much as possible the process of deciding another unit to which the partial data with the bit immediately after the last bit as the first bit is distributed as the new adopted unit Collecting numerical data that has been successfully decoded in each selected unit, and generating a decoded data string by arranging the numerical data based on the information collected by one or more parallel processes. An apparatus for decoding a numerical data string characterized by The decoding device according to claim 25 ,
Each time the M decoding processing units perform distribution of new partial data, the process for extracting the numerical data corresponding to the run length value and the actual data from the head of the distributed partial data is normally performed. And a decoding apparatus for a numerical data string, characterized in that a simple decoding process is continued as much as possible. The decoding device according to claim 25 ,
Each time each of the M decoding processing units distributes the new partial data, only the run length value and the numerical data corresponding to the actual data for one unit code data from the head of the distributed partial data. A numerical data string decoding apparatus, characterized by performing a process for extracting data. The decoding device according to claim 25 ,
Among the M decoding processing units, each of the first to (M−1) -th units is 1 from the head of the distributed partial data each time new partial data is distributed. A process for extracting only numerical data corresponding to run length values and actual data for one unit code data is performed, and each time the M-th unit distributes new partial data, the distributed part An apparatus for decoding a numerical data string, characterized in that a process for extracting numerical data corresponding to a run length value and actual data from the beginning of data is continued as long as normal decoding processing is possible. The decoding device according to any one of claims 25 to 28 ,
Each of the M decoding processing units executes a process of restoring the original data by arranging the numerical data corresponding to the actual data after arranging the numerical data indicating 0 for the number of times corresponding to the run length value, The restored data is given to the data organization department,
A numerical data sequence decoding apparatus, wherein the data organization unit generates a decoded data sequence by arranging data provided from each decoding processing unit. The decoding device according to any one of claims 25 to 28 ,
Each of the M decoding processing units gives the run length value and the numerical data corresponding to the actual data as they are to the data organization unit,
The data organization unit arranges the numerical data corresponding to the actual data after arranging the numerical data indicating 0 based on the information given from each adopted unit, and arranging the numerical data corresponding to the run-length value. An apparatus for decoding a numerical data string, wherein a decoding data string is generated by executing a restoring process and arranging the restored data. The decoding device according to any one of claims 25 to 30 ,
When a data file including an encoded data string and an encoding table used for encoding processing is given,
The data storage unit performs a process of extracting and storing the encoded data string from the data file,
A numerical data string decoding apparatus, wherein a table storage unit performs a process of extracting and storing an encoding table from the data file. The decoding device according to any one of claims 25 to 30 ,
When a data file including an encoded data string and table specifying information for specifying an encoding table used for encoding processing is given,
The data storage unit performs a process of extracting and storing the encoded data string from the data file,
Decoding of a numerical data string, wherein a table storage unit performs processing for extracting table specifying information from the data file and then reading and storing a table specified by the table specifying information from the outside Device. The decoding device according to any one of claims 25 to 32 ,
A numerical data string decoding apparatus comprising a plurality of M decoding processing units such that M ≧ 1 + L / N. The decoding device according to any one of claims 25 to 33 ,
Each decoding processing unit has a function of reporting to the data organization unit information obtained by normal decoding processing and a normal processing bit length indicating the number of bits involved in the normal decoding processing,
An apparatus for decoding a numerical data sequence, wherein a data organization unit determines an adopted unit based on the reported normal processing bit length, and generates a decoded data sequence using the reported information. The decoding device according to claim 34 ,
Each time the data organization unit obtains the processing results from the M decoding processing units by one parallel processing, it recognizes the already-decoding unit by summing the normal processing bit lengths reported from each adopted unit. , Has a function to report this to the data distribution unit,
The data distribution unit recognizes an undecoded unit for the next parallel processing based on the report, and decodes a numerical data string. 36. A program that causes a computer to function as an encoding device or a decoding device for a numerical data string according to any one of claims 18 to 35 . The numerical data string encoding device according to claim 18 is used as DC component numerical data encoding means, and the numerical data string encoding device according to claim 19 is used as AC component numerical data string encoding means. A compression processing apparatus for JPEG images, characterized by being used as: The decoding device for the numerical data sequence described in (1) below is used as a decoding means for the numerical data of the DC component, and the decoding device for the numerical data sequence described in (2) is used as the numerical data sequence for the AC component. A decompression processing apparatus for JPEG images, characterized in that it is used as a decoding means.
(1) “A data in which actual data consisting of a bit string having the bit length is arranged following an identification code indicating a predetermined bit length, and the total length is a predetermined reference bit length N (where N is 2 or more) Numerical data corresponding to individual actual data is restored for an encoded data string formed by arranging a plurality of sets of unit code data (maximum bit length Umax) set to be an integer multiple of (integer)) A decryption device for
A data storage unit for inputting and storing an encoded data sequence to be decoded;
A table storage unit for storing a coding table indicating a specific bit length corresponding to each identification code;
A plurality of M decoding processing units that perform decoding processing on continuous bit data of L bits (where L is an integer multiple of N and L ≧ Umax) in parallel,
A data distribution unit that distributes a part of the encoded data sequence stored in the data storage unit as partial data to the M decoding processing units;
A data organization unit that selects a result of the decryption processing by the M decryption processing units and generates a decrypted data sequence in which numerical data corresponding to individual actual data are arranged;
A data output unit for outputting the generated decoded data sequence;
With
The data distribution unit counts from the (N × (i−1) +1) th bit to the (N × (i−1) + L) th bit counted from the beginning of the undecoded portion of the encoded data string. The process of distributing the bit string to the i-th unit (i = 1 to M) is repeated until decoding of all parts of the encoded data string is completed,
The M decoding processing units have a function of performing a decoding process of extracting numerical data corresponding to actual data from each distributed partial data while referring to the encoding table, and distributing new partial data Is performed, the process to extract the numerical data corresponding to the actual data from the beginning of the distributed partial data,
When the processing result is obtained from the M decoding processing units by one parallel processing, the data organization unit first determines the first unit as the first selected unit, and the selected unit performs normal decoding. Recognize the last bit that has been processed, and continue as much as possible the process of deciding another unit to which the partial data with the bit immediately after the last bit as the first bit is distributed as the new adopted unit , Collecting numerical data successfully decoded in each selected unit, and generating a decoded data string by arranging the numerical data collected by one or more parallel processes, respectively Decoding device for numeric data string.
(2) The numerical data string decoding device according to any one of claims 25 to 30. A computer-readable information recording medium on which a data file output by the encoding method according to claim 4 is recorded.

Images