JP4497029B2 - Data encoding apparatus and data encoding method - Google Patents

Description

  The present invention relates to a data encoding device that encodes data, a data decoding device that decodes encoded data, and a method thereof.

  Conventionally, as a method for compressing / decompressing data without distortion, a technique called Huffman code described below has been proposed (see, for example, Patent Document 1). For example, it is assumed that the data to be compressed is a series of N-value symbols (for example, an English sentence is a series of alphabets (26 + 3 (space, period, comma) -value symbols)). The Huffman coding roughly takes the following procedures (1) to (4).

(1) Check the appearance probability of each symbol of data to be compressed.
(2) Using the appearance probability, create a coding table so that a codeword with a short code length is assigned to a symbol with a high appearance probability and a codeword with a long code length is assigned to a symbol with a low appearance probability. To do.
(3) The encoding table is drawn for each symbol of the data to be compressed and encoded into a corresponding code word.
(4) The encoding table information corresponding to the encoding table is added to the head of the encoded data.

This encoding table information includes the following two pieces of information.
(I) Information indicating the number of codewords of each code length (II) Symbol information arranged in order of appearance probability

Further, when decoding the encoded sequence, the following procedures (1) to (2) are roughly taken.
(1) Generate an encoding table from the encoding table information at the head of the encoded data.
(2) Draw a coding table and decode a symbol for a codeword.

Japanese Patent Laid-Open No. Hei 8-162973

However, the above method has a problem that, as the number of symbols increases, “(II) symbol information arranged in order of appearance probability” increases in the encoding table information. For example, if all the values represented by 16 bits are assigned to a symbol, the number of symbols is 2 ¹⁶ = 65536, and if the order of appearance probability is to be represented, 65536 × 16 = 1048576 bits are required. turn into.

  Therefore, the present invention has been made in view of such problems, and an object of the present invention is to use a data encoding device that generates encoding table information with a reduced amount of information, and the encoding table information. It is another object of the present invention to provide a data decoding apparatus and a method for decoding the data.

  In order to solve at least one of the above problems, according to an aspect of the present invention, there is provided a data encoding apparatus for encoding a symbol, wherein an appearance frequency of each symbol value of a fixed number of symbols input from the outside. And encoding information related to the codeword length of the codeword in which each symbol is encoded based on the calculated cumulative frequency of occurrence of each symbol value and a predetermined target cumulative value Provided is a data encoding device comprising: a cumulative appearance frequency distribution measurement unit that is generated as table information; and an encoding unit that encodes each of the symbols using the generated encoding table information Is done.

  According to this, the encoding table information is generated based on the cumulative value of the appearance frequency of each symbol and the predetermined target cumulative value. This encoding table information is information related to the codeword length of the codeword in which each symbol is encoded, and does not include the “symbol information arranged in order of appearance probability” included in the conventional encoding table information. . As a result, the amount of information held in the encoding table information can be reduced. In particular, “symbol information arranged in the order of appearance probability” has a huge amount of information as the number of symbols to be encoded increases. For this reason, especially when the number of symbols to be encoded is large, the information amount of the encoding table information of the present invention can be greatly reduced as compared with the conventional encoding table information. The “appearance frequency of each symbol value” may be, for example, the appearance probability of each symbol value or the number of appearances (number of appearances) of each symbol value.

  The cumulative appearance frequency distribution measurement unit accumulates the appearance frequency of each symbol value in ascending order from an arbitrary symbol value (for example, the smallest symbol value), and the accumulated value becomes a value closest to the target cumulative value. The loop processing for obtaining the number of bits Li required to encode and represent the symbol value for which the cumulative value is to be obtained is repeated until a predetermined condition is satisfied, and the number of iterations k and each of the loop processing are obtained. The number of bits Li (i = 1, 2,..., K) may be generated as the encoding table information.

  At this time, a maximum value detecting unit for detecting a maximum value of a certain number of symbols input from the outside is provided, and the cumulative appearance frequency distribution measuring unit is configured such that the maximum value of the detected symbols satisfies the predetermined condition. Up to this point, the above loop processing may be repeated.

  In addition, the target cumulative value used at this time may be a value that decreases each time the loop processing is repeated.

  Further, the coding table information may be information generated for every power of 2 in order to represent the code word length that changes for every power of 2 corresponding to each symbol value.

  Further, the encoding unit may encode the symbols by applying the encoding table information to the conditional expressions shown by the following methods B (1) to B (4).

That is, specific methods of B (1) to B (4) are as follows.
B (1) When k = 1, a code word is simply a binary representation of the symbol X.
B (2) When k> 1, first, the following range is determined and i is specified.
_{i-1 i}
Σ 2 ^Lj to Σ 2 ^Lj −1
^{j = 1 j = 1}
B (3) The next value X ′ is obtained.
_i-1
X ′ = X−Σ 2 ^Lj + 1
^{j = 1}
B (4) If i <k, 1 ⁽ⁱ⁻¹⁾ 0 ( ^i.e. , 1 after adding 1 after adding 1 to ¹⁾ is added to the beginning of the binary representation of X ′ with L _i bits. The added word is a code word. In addition, when i = k, a code word is obtained by adding 1 ^k−1 (k−1 consecutive 1s) to the beginning of X ′ representing L _k bits in a binary number.

  Each symbol value may be a positive value of 0 or more. Consider a case where the appearance probability of a symbol of data to be compressed has the following specialities. For example, physical environment measurement values such as temperature, humidity, and small shaking generated in a building are considered to be continuous values, and the case of sampling at a certain frequency is considered. Specifically, this is a case where a minute shaking generated in a building is measured every second. Such measurement values can be expected to concentrate on a value close to 0 when taking a difference from the previous measurement value in time series. When such an absolute value of difference values (that is, a positive value of 0 or more) is considered as one symbol, it is considered that “appearance probability is higher as the value is closer to 0”, and coding table information that has been necessary in the past. Of these, “symbol information arranged in the order of appearance probability” can be replaced with “arranged in ascending order of value”.

  Further, if the number of codewords having a codeword length of L can be calculated from L or another codeword length in the encoding table, “information indicating the number of codewords of each code length” in the encoding table information. "Only needs to list the codeword lengths used in the codewords constituting the encoding table. As a result, the information amount of the encoding table information can be significantly reduced from the information amount of the conventional encoding table information.

  Furthermore, the data encoding device includes an encoding table information holding unit that holds the generated encoding table information, and the encoding unit receives one or more newly input symbols from the outside. You may make it encode using the encoding table information hold | maintained at the encoding table information holding part.

  The data encoding device further includes a storage unit that stores, for each symbol value, the appearance frequency of each symbol value of a certain number of symbols including one or more newly input symbols from the outside this time, The cumulative appearance frequency distribution measuring unit calculates an appearance frequency of each symbol value stored in the storage unit, and encodes a coding table based on the calculated cumulative value of the appearance frequency of each symbol and the target cumulative value. The coding table information holding unit holds the generated coding table information, and the coding unit stores one or more newly input symbols from the outside next time as the code. Encoding may be performed using the encoding table information held in the encoding table information holding unit.

  According to this, encoding table information is generated from W symbols preceding the symbol to be encoded (for example, W symbols inputted most recently). Thereby, also in the data decoding apparatus which decodes the data encoded by the data encoding apparatus, the encoding table information can be generated from the already decoded symbols. For this reason, the data encoding apparatus needs to include the encoding table information in the encoded data transmitted to the data decoding apparatus after that, only by transmitting the encoding table information to the data decoding apparatus only once at the beginning. Disappear. As a result, the overhead of the data encoding device can be reduced. Note that the number of one or more symbols newly input from the outside may be a fixed number.

Furthermore, instead of storing the appearance frequency of each symbol value for each symbol value, the storage unit sequentially sets each symbol value to a power of 2 (2 ⁱ : i = 0, 1, 2,. -) May be divided every time, the frequency of appearance of each symbol value in the division may be accumulated for each division, and the accumulated value may be stored.

  According to this, the memory area for storing the appearance frequency of the symbol value for each symbol value can be reduced. In addition, since the number of repetitions of the loop processing performed by the cumulative appearance frequency distribution measuring unit is reduced, the load on the CPU can be reduced.

  According to another aspect of the present invention, there is provided a data decoding apparatus for decoding a codeword in which symbols are encoded, and a predetermined number of codewords transmitted from the data encoding apparatus and codes of the respective codewords And a decoding unit that inputs encoding table information indicating information related to word length and decodes each of the input codewords into each symbol using the input encoding table information. A data decoding device is provided.

  According to this, the input coding table information is information related to a certain number of code words and the code word length of each code word, and the previously included “symbol information arranged in order of appearance probability” is included. Not included. As a result, it is possible to receive the encoding table information having a very compact amount of information from the data encoding device, and to decode each input codeword into each symbol using the received encoding table information. it can.

  The decoding unit extracts a part necessary for decoding a symbol from the input codeword using the input encoding table information, and uses the extracted part and the encoding table information to extract each part described above. The codeword may be decoded into each symbol.

  Alternatively, the data decoding device includes a coding table information holding unit that holds the coding table information, and a fixed number of symbols (for example, one or more symbols newly transmitted from the data coding device this time (for example, A storage unit that stores the appearance frequency of each symbol value), and the cumulative appearance frequency distribution measurement unit stores each symbol value stored in the storage unit. Based on the cumulative value of the appearance frequency and a predetermined target cumulative value, new encoding table information is generated, and the encoding table information holding unit holds the generated new encoding table information, The decoding unit may decode a codeword newly transmitted from the data encoding device next time into a symbol using the held encoding table information.

  Further, the data decoding device includes an encoding table information holding unit for holding the coding table information, and the cumulative appearance frequency distribution measuring unit is configured to receive a certain number of symbols newly transmitted from the data encoding device this time. The frequency of appearance of each symbol value is calculated, new coding table information is generated based on the calculated cumulative value of the appearance frequency of each symbol value and the target cumulative value, and the coding table information holding unit Holds the generated new encoding table information, and the decoding unit decodes a codeword newly transmitted from the data encoding device next time into a symbol using the held encoding table information. You may make it do.

  According to this, encoding table information is generated from W symbols preceding the symbol to be encoded. Thereby, also in the data decoding apparatus which decodes the data encoded by the data encoding apparatus, the encoding table information can be generated from the already decoded symbols. For this reason, it is only necessary to receive the encoding table information from the data encoding device only once at the beginning. As a result, in the first decoding process, the decoding unit transmits a fixed number of code words and encoding table information from the data encoding device, and uses the transmitted encoding table information to transmit each of the transmitted The codeword is decoded into each symbol, and in the subsequent decoding process, only one or two or more codewords are transmitted from the data encoding apparatus, and each transmitted codeword is sent to the encoding table information holding unit. Each symbol can be decoded using the held coding table information.

  In addition, instead of storing the appearance frequency of each symbol value for each symbol, the storage unit delimits each symbol value in powers of 2 in order from the smallest symbol value, and the appearance frequency of each symbol value within the division May be accumulated, and the accumulated values may be stored respectively.

  According to this, the memory area for storing the appearance frequency of the symbol value for each symbol value can be reduced. In addition, since the number of repetitions of the loop processing performed by the cumulative appearance frequency distribution measuring unit is reduced, the load on the CPU can be reduced.

  According to another aspect of the present invention, there is provided a data encoding method for encoding a symbol, calculating an appearance frequency of each symbol value of a fixed number of symbols input from the outside, and calculating each of the calculated values Based on the cumulative value of the appearance frequency of the symbol value and a predetermined target cumulative value, information related to the codeword length of the codeword in which each symbol is encoded is generated as the encoding table information, and is generated as described above. There is provided a data encoding method characterized by encoding each symbol using the encoding table information.

  According to another aspect of the present invention, there is provided a data decoding method for decoding a codeword in which a symbol is encoded, and a predetermined number of codewords transmitted from a data encoding device and codes of the respective codewords Data decoding method characterized by inputting coding table information indicating information related to word length and decoding each inputted code word into each symbol using the inputted coding table information Is provided.

  As described above, according to the present invention, a data encoding apparatus that generates encoding table information with a reduced amount of information, a data decoding apparatus that decodes data using the encoding table information, and methods thereof are provided. Can be provided.

  Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the present specification and drawings, components having substantially the same functional configuration are denoted by the same reference numerals, and redundant description is omitted.

(First embodiment)
First, each configuration of the data encoding device and the data decoding device according to the first embodiment of the present invention will be described with reference to the configuration diagrams shown in FIGS. 1 and 2, respectively. The data encoding device and the data decoding device are connected via a network (not shown).

(Configuration of data encoding device)
A data encoding apparatus 100 (data compression encoding apparatus) shown in FIG. 1 compresses and encodes a symbol sequence of data input from the outside. The symbol sequence input to the data encoding device 100 is a positive integer greater than or equal to 0, such as a difference value (absolute value of the difference value) of environmental measurement values such as temperature, humidity, and minute vibration of a building. A symbol series of data that appears more as the value is closer to 0. The data encoding apparatus 100 detects the appearance frequency and maximum value of each symbol value for each W symbols in such a symbol series, generates encoding table information based on the detected frequency, and generates the encoding table information. The W symbols are encoded using the encoding table information.

  The data encoding apparatus 100 includes a buffer 101, a maximum value detection unit 102, a cumulative appearance frequency distribution measurement unit 103, and an encoding unit 104. The buffer 101 receives a symbol sequence input to the data encoding apparatus 100, and holds W symbols (data) necessary for generating an encoding table. Further, the buffer 101 outputs the held symbol series to the encoding unit 104 when encoding the symbols. The buffer 101 corresponds to a storage unit of the data encoding device 100.

The maximum value detection unit 102 detects the symbol having the maximum value among the W symbols, and outputs the symbol value (maximum value) to the cumulative appearance frequency distribution measurement unit 103. The cumulative appearance frequency distribution measurement unit 103 observes W symbols and uses the maximum value output from the maximum value detection unit 102 to calculate a cumulative appearance frequency distribution of the following A (1) to A (4). K and L _i (i = 1, 2,..., K) obtained as a result of the calculation are output to the encoding unit 104 as encoding table information.

The methods A (1) to A (4) are as follows.
A (1) k = 1 and C = 0.
A (2) The appearance frequency (number of appearances) is accumulated in order from the symbol C, and the symbol X whose accumulated value is closest to W / ^2k is ^obtained .
A (3) The number of bits L _k necessary to represent the value of (X−C + 1) is _obtained .
A (4) When the maximum value is between C and C + 2 ^Lk −1, the process is terminated. Otherwise, set the value obtained by C + 2 ^Lk to C, increase k by 1, and return to A (2).

When the above method is executed, encoding table information k, L _i (i = 1, 2,..., K) having the relationship shown in the table of FIG. 6 is obtained. Specific processing using A (1) to A (4) will be described later.

The encoding unit 104 uses the encoding table information k, L _i (i = 1, 2,..., K) received from the cumulative appearance frequency distribution measurement unit 103 to convert the symbol received from the buffer 101 as follows. Compression encoding is performed in steps B (1) to B (4), and the compression encoded sequence is output.
B (1) When k = 1, a code word is simply a binary representation of the symbol X.
B (2) When k> 1, first, the following range is determined and i is specified.
_{i-1 i}
Σ 2 ^Lj to Σ 2 ^Lj −1
^{j = 1 j = 1}
B (3) The next value X ′ is obtained.
_i-1
X ′ = X−Σ 2 ^Lj + 1
^{j = 1}
B (4) If i <k, 1 ⁽ⁱ⁻¹⁾ 0 ( ^i.e. , 1 after adding 1 after adding 1 to ¹⁾ is added to the beginning of the binary representation of X ′ with L _i bits. The added word is a code word. In addition, when i = k, a code word is obtained by adding 1 ^k−1 (k−1 consecutive 1s) to the beginning of X ′ representing L _k bits in a binary number.

  In this way, the data encoding device 100 compresses and encodes symbols (data).

(Configuration of data decoding device)
The data decoding device 200 (data decompression decoding device) shown in FIG. 2 decompresses and decodes the data compressed and encoded by the data encoding device 100. The data decoding device 200 is configured to include a decoding unit 201. The decoding unit 201 receives encoded data (encoding table information (k, and L _i (i = 1, 2,..., K)) and an encoded symbol sequence), and refers to the encoding table information. However, a code word is extracted from the encoded symbol sequence, converted into a corresponding symbol, and output.

Specifically, a codeword of a portion necessary for symbol decoding is cut out and converted into a symbol X in the following steps C (1) to C (3).
For C (1) k = 1, at the codeword length L _1, cut codeword portions necessary for decoding of the symbol, as it is a binary representation of the symbols back to the symbol.
When C (2) k> 1, when the first bit is 1 ⁽ⁱ⁻¹⁾ 0 (i = 1, 2,..., K−1), 1 ⁽ⁱ⁻¹⁾ 0 (i = 1, 2,..., K-1) is followed by a codeword length _Li , and a codeword of a part necessary for symbol decoding is cut out, and a numerical value expressed as a binary representation is set as X '. When the first bit is 1 ^k−1 , the code word length L _k is followed by a part of the code word necessary for decoding the symbol, and a numerical value represented as a binary representation is expressed as X ′ far.
C (3) The next value X is calculated and used as a symbol to be decoded.
_i-1
X = X ′ + Σ 2 ^Lj + 1
^{j = 1}

  The data decoding apparatus 200 is configured to decompress and decode the data compressed and encoded by the data encoding apparatus 100 in this way.

  Each of the data encoding device 100 and the data decoding device 200 includes a CPU, a ROM, an interface, and the like (not shown), and each ROM stores a program and various data for executing each function of each device. Each is remembered. Each CPU achieves the function of each device by executing information about symbols held in the buffer and each program stored in each ROM.

(Operation of Data Encoding Device 100)
Next, the data encoding apparatus 100 inputs _W symbols (X _{1 to} X _w ) in the symbol sequence of FIG. 3 and performs compression encoding processing to be executed on these symbols in the flowchart of FIG. Will be described with reference to FIG.

First, the CPU of the data encoding apparatus 100 starts processing from step S400, proceeds to step S401, and determines whether there is a symbol to be compression encoded. At this point, if there are _W symbols (X _{1 to} X _w ) in FIG. 3, the CPU determines “Yes” in step S 401, proceeds to step S 402, and stores the W symbols in the buffer 101. Read. When the number of symbols to be compression-encoded is less than W, W in the subsequent steps is the number. In the following description, W is assumed to be “1000”.

  Next, the CPU proceeds to step S403 and obtains the number of appearances of each read symbol. Here, in order to simplify the description, as shown in FIG. 5, the value of the symbol C is “0”, “1”, “2”, “3”, “4”, “5”, “6”. ”. As a result of executing step S403, the number of appearances SUM (C) of each symbol is SUM (0) = 400, SUM (1) = 300, SUM (2) = 150, SUM (3) = 100, SUM ( 4) = 30, SUM (5) = 10, SUM (6) = 10. The appearance number SUM of each symbol value is an example of the appearance frequency of each symbol value.

  Next, the CPU (maximum value detection unit 102) proceeds to step S404 in FIG. 4, and sets the maximum value of the read 1000 symbols to Cmax. Here, the maximum value of the read symbol is “6”. Therefore, the CPU (maximum value detection unit 102) sets “6” to Cmax, and proceeds to step S405.

Next, the CPU (cumulative appearance frequency distribution measurement unit 103) sets “1” to k and “0” to C as initial settings in step S405. This corresponds to A (1) described above. Next, the CPU (cumulative appearance frequency distribution measuring unit 103) proceeds to step S406, accumulates the number of appearances in order from the symbol C (the number of occurrences of the symbol 0, which is the minimum value of the symbol at this time), and the accumulated value AC. but finding a symbol X, which has become the place closest to the W / 2 ^k. This corresponds to A (2) described above. Note that W / ^2k is an example of a predetermined target cumulative value, and is a value that decreases as the loop processing of A (2) to A (4) is repeated.

Specifically, as shown in FIG. 5, the value of SUM (0) (cumulative value AC) is 400, and the cumulative value AC of SUM (0) to SUM (1) is 700. Therefore, the CPU (cumulative appearance frequency distribution measuring unit 103) determines the symbol whose accumulated value AC is closest to W / 2 ^k (= 500) as symbol 0 and substitutes a value of “0” for X. To do.

Next, the CPU (cumulative appearance frequency distribution measurement unit 103) proceeds to step S407, and sets the number of bits necessary to represent the value of (X−C + 1) to L _k . This corresponds to A (3) described above. At this time, X−C + 1 = 0−0 + 1 = 1. Since the number of bits necessary to represent this value “1” is one bit, the CPU (cumulative appearance frequency distribution measurement unit 103) sets a value of “1” to L _k (= L ₁ ).

Next, the CPU (cumulative appearance frequency distribution measuring unit 103) proceeds to step S408, and the maximum value Cmax detected in step S404 is obtained from L _i (i = 1, 2,..., K) calculated in step S407. The following range,
_{k-1 k}
Σ2 ^Lj to Σ2 ^Lj −1
^{j = 1 j = 1}
It is determined whether it is in. That is, the CPU (cumulative appearance frequency distribution measurement unit 103) determines whether or not the maximum value Cmax satisfies the condition of C ≦ Cmax ≦ C + 2 ^Lk −1. This corresponds to A (4) described above.

At this point, C = 0 and L _k (= L ₁ ) = 1. Substituting these values into the above conditions satisfies the requirement of C (= 0) ≦ Cmax (= 6), but Cmax (= 6)> C + 2 ^Lk −1 (= 0 + 2-1 = 1), and Cmax ≦ The condition of C + 2 ^Lk −1 is not satisfied. Therefore, the CPU (cumulative appearance frequency distribution measuring unit 103) determines “No” in step S408, proceeds to step S409, sets the value “2” of C + 2 ^L1 (= 0 + 2 ¹ ) to C, k is incremented by 1 (ie, k = 2), and the process returns to step S406. Thus, as a result of completing the first loop, L ₁ = 1 was obtained as the encoding table information.

Next, in step S406, the CPU (cumulative appearance frequency distribution measuring unit 103) accumulates the number of appearances in order from the symbol C (the number of occurrences of symbol 2 at this time), and the accumulated value AC is reduced to W / ^2k . Find the nearest symbol X. Specifically, as shown in FIG. 5, the value (cumulative value AC) of SUM (2) is 150, the cumulative value AC of SUM (2) to SUM (3) is 250, SUM (2) to SUM ( The cumulative value AC of 4) is 280. Therefore, the CPU (cumulative appearance frequency distribution measuring unit 103) determines the symbol whose cumulative value AC is closest to W / 2 ^k (= 250) as symbol 3 (that is, X = 3).

Next, the CPU (cumulative appearance frequency distribution measurement unit 103) proceeds to step S407 and sets the number of bits “1” necessary to represent the value “2” of (X−C + 1 (= 3−2 + 1)) to L _k. Set to (= L ₂ ).

Next, the CPU (cumulative appearance frequency distribution measurement unit 103) proceeds to step S408, and determines whether or not the maximum value Cmax satisfies the condition of C ≦ Cmax ≦ C + 2 ^Lk −1. At this point, C = 2 and L ₂ = 1. If these values are substituted into the above conditions, Cmax (= 6)> C + 2 ^Lk −1 (= 2 + 2-1 = 3), and the condition of Cmax ≦ C + 2 ^Lk −1 is not satisfied. Therefore, the CPU (cumulative appearance frequency distribution measurement unit 103) determines “No” in step S408, proceeds to step S409, sets the value “4” of C + 2 ^L2 to C, and increases k by one. (That is, k = 3), the process returns to step S406. In this way, as a result of completing the second loop, L ₂ = 1 was obtained as the encoding table information.

Next, in step S406, the CPU (cumulative appearance frequency distribution measuring unit 103) accumulates the number of appearances in order from the symbol C (the number of occurrences of the symbol 4 at this time), and the accumulated value AC is reduced to W / ^2k . Find the nearest symbol X. Specifically, as shown in FIG. 5, the value (cumulative value AC) of SUM (4) is 30, the cumulative value AC of SUM (4) to SUM (5) is 40, and SUM (4) to SUM ( The cumulative value AC of 6) is 50. Therefore, the CPU (cumulative appearance frequency distribution measurement unit 103) determines the symbol whose cumulative value AC is closest to W / 2 ^k (= 125) as symbol 6 (ie, X = 6).

Next, the CPU (cumulative appearance frequency distribution measuring unit 103) proceeds to step S407 and sets the number of bits “2” necessary to represent the value “3” (= 6-4 + 1) of (X−C + 1) to L _k. Set to (= L ₃ ).

Next, the CPU (cumulative appearance frequency distribution measurement unit 103) proceeds to step S408, and determines whether or not the maximum value Cmax satisfies the condition of C ≦ Cmax ≦ C + 2 ^Lk −1. At this point, C = 4 and L ₂ = 2. Therefore, C (= 4) ≦ Cmax (= 6) ≦ C + 2 ^Lk −1 (= 4 + 4−1 = 7), and the condition is satisfied. Therefore, the CPU (cumulative appearance frequency distribution measurement unit 103) determines “Yes” in step S408, and proceeds to step S410. As a result of completing the third loop, L ₃ = 2 was obtained as the encoding table information. In addition, as a result of executing the loop processing 1 to 3 times in this way, coding table information having values of k = 3, L ₁ = 1, L ₂ = 1, and L ₃ = 2 was obtained.

In step S410, the CPU (encoding unit 104) encodes W symbols using the encoding table information (k = 3, L ₁ = 1, L ₂ = 1, L ₃ = 2). The encoded sequence of W symbols and encoding table information are output as encoded data. A specific method for encoding W symbols using the encoding table information (k = 3, L ₁ = 1, L ₂ = 1, L ₃ = 2) will be described later.

  Next, the CPU returns to step S401 and determines whether there is a symbol to be compression encoded. At this time, if there is no symbol to be compression-encoded, the CPU makes a “No” determination, proceeds to step S411, and ends this processing.

(Compression coding of symbols)
Next, specific methods B (1) to B (4) of the symbol compression encoding performed by the CPU (encoding unit 104) in step S410 will be described. The codeword (encoded symbol) in FIG. 6 is a binary codeword (a codeword consisting of a sequence of 0 and 1). When m 1s or 0s continue, ^1m or ^0m Is written.

B (1) When k = 1, a code word is simply a binary representation of the symbol X. In the above process, the coding table information is k = 3, L ₁ = 1, L ₂ = 1, and L ₃ = 2. Accordingly, since k ≠ 1, in this case, the symbol X is converted into a code word by the following B (2) to B (4).
B (2) When k> 1, first, the following range is determined and i is specified.
_{i-1 i}
Σ 2 ^Lj to Σ 2 ^Lj −1
^{j = 1 j = 1}
B (3) The next value X ′ is obtained.
_i-1
X ′ = X−Σ 2 ^Lj + 1
^{j = 1}
B (4) When i <k, 1 ^(i-1) 0 is added to the beginning of a binary representation of X 'with L _i bits ⁽ 0 is added after 1 consecutive 1s) Is a code word. In addition, when i = k, a code word is obtained by adding 1 ^k−1 (k−1 consecutive 1s) to the beginning of X ′ representing L _k bits in a binary number.

As a result, as shown in FIG. 7, when the symbol is 0 to 2 ^L1 −1 (that is, 0 to 1), the code word for symbol 0 is generated as “00”, and the code word for symbol 1 is “01”. Is generated. When the symbol is 2 ^{L1 to} 2 ^L1 +2 ^L2 −1 (ie, 2 to 3), the code word for symbol 2 is generated as “100”, and the code word for symbol 3 is generated as “101”. Further, when the symbol is 2 ^L1 +2 ^L2 to 2 ^L1 +2 ^L2 +2 ^L3 −1 (ie, 4 to 7), the codeword for symbol 4 is generated as “11000”, and the codeword for symbol 5 is “11001”. The code word for symbol 6 is generated as “11010”. “11001” is a missing number.

In this way, the CPU (encoding unit 104) encodes each symbol, and encodes a sequence of encoded symbols into encoding table information (k, _Li (i = 1, 2,..., K)), that is, Output with k = 3, L ₁ = 1, L ₂ = 1, L ₃ = 2.

(Symbol expansion decoding)
Next, the operation of the data decoding apparatus 200 in the first embodiment will be described. The CPU (decoding unit 201) of the data decoding apparatus 200 receives the encoding table information (k = 3, L ₁ = 1, L ₂ = 1, L ₃ = 2) and the sequence of encoded symbols, Using the methods C (1) to C (3), while referring to the coding table information, the codeword of the part necessary for decoding the symbol is extracted from the encoded symbol sequence and converted into the corresponding symbol. Output.

Specifically, the code word is cut out and converted to the symbol X in the following steps.
For C (1) k = 1, at the codeword length L _1, cut codeword portions necessary for decoding of the symbol, it is returned to the symbol as has become binary representation of the symbols.
When C (2) k> 1, when the first bit is 1 ⁽ⁱ⁻¹⁾ 0 (i = 1, 2,..., K−1), 1 ⁽ⁱ⁻¹⁾ 0 (i = 1, 2,..., K-1) is followed by a codeword length _Li , and a codeword of a part necessary for symbol decoding is cut out, and a numerical value expressed as a binary representation is set as X '. When the first bit is 1 ^k−1 , the code word length L _k is followed by a part of the code word necessary for decoding the symbol, and a numerical value represented as a binary representation is expressed as X ′ far.
C (3) The next value X is calculated and used as a symbol to be decoded.
_i-1
X = X ′ + Σ 2 ^Lj + 1
^{j = 1}
By such a method, the data decoding apparatus 200 decodes each symbol from each codeword shown in FIG.

According to the data encoding device 100 and the data decoding device 200 according to the first embodiment, the symbol of the data to be compressed is a positive value of 0 or more, and the appearance probability is higher as the appearance characteristic is closer to 0. In the case of compression encoding, “symbol information arranged in the order of appearance probability” is unnecessary among the encoding table information that has been conventionally required. Furthermore, since the number of codewords having the codeword length can be calculated from the codeword length (L _i (i = 1, 2,..., K)), among the encoding table information that has conventionally been required, “ The “information indicating the number of codewords of each code length” simply lists the codeword lengths (L _i (i = 1, 2,..., K)) used in the codewords constituting the encoding table. Good. As a result, the information amount of the encoding table information can be greatly reduced.

(Second Embodiment)

  Next, the data encoding device 100 and the data decoding device 200 according to the second embodiment will be described. In the data encoding apparatus 100 according to the first embodiment, encoding table information is generated for each W symbols to be encoded, each symbol is encoded, and the encoded table information is encoded along with the encoded symbols. Needed to be included.

In the second embodiment, as shown in FIG. 10, encoding table information is generated from W symbols (X _{1 to} X _w ) preceding the symbol to be encoded (X _{w + 1} to). Here, the symbol to be encoded is, for example, if the parameter information transmitted from the data encoding apparatus 100 is “1”, it is one symbol indicated by X _{w + 1 in} FIG. If the parameter information transmitted from the data encoding apparatus 100 is “W”, W symbols indicated by X _{w + 1 to} X _{2w in} FIG. 10 are obtained. As a result, the data decoding apparatus 200 can generate the encoding table information from the already decoded symbols, and there is no need to receive the encoding table information as encoded data. The parameter information indicates a symbol delimiter to be input for one encoding process in a symbol series to be encoded. As described above, a method according to the second embodiment that performs compression encoding and decompression decoding that do not require encoding table information to be included in encoded data will be described.

(Configuration of data encoding device)
First, the configuration of the data encoding device 100 according to the second embodiment will be described with reference to FIG. The data encoding apparatus 100 according to the second embodiment includes a buffer 101, a maximum value detection unit 102, a cumulative appearance frequency distribution measurement unit 103, an encoding unit 104, and an encoding table information holding unit 805.

  The input to the data encoding apparatus 100 is a symbol series of data to be compression encoded, as in the first embodiment, and each symbol takes a positive integer of 0 or more. The symbol sequence detects the appearance frequency and maximum value of each W symbol, generates encoding table information based on the detected frequency, and encodes the W symbols using the encoding table information. Turn into.

  The buffer 101 is a memory that can hold the latest W symbols input to the data encoding device 100. Further, the buffer 101 stores the appearance frequency of each symbol value of the latest W symbols. The contents of the buffer 101 are referred to from the maximum value detection unit 102 and the cumulative appearance frequency distribution measurement unit 103.

The maximum value detection unit 102 detects a symbol having the maximum value among the W symbols in the buffer 101 and outputs the symbol value to the cumulative appearance frequency distribution measurement unit 103. The cumulative appearance frequency distribution measurement unit 103 observes W symbols in the buffer 101 and uses the maximum value output from the maximum value detection unit 102 to calculate the cumulative appearance frequency distributions A (1) to A ( 4), and finally obtained k and L _i (i = 1, 2,..., K) are output to the encoding table information holding unit 805 as encoding table information.

The encoding unit 104 receives the encoding table information k, L _i (i = 1, 2,..., K) held in the encoding table information holding unit 805, and uses the received encoding table information to perform data The symbols input to the encoding device 100 are compression encoded.

Specifically, the encoding unit 104 converts a symbol into a code word in the above-described steps B (1) to B (4). However, this also applies to the case where B (1) is deleted and B (2) is k = 1. Further, in the process of B (4), even when i = k, 1 ^(i-1) 0 (1 is continued by ^{i-1) at the} head of the X 'representing the binary representation of L _i bits. A code word is added with 0 added later).

Also, if the symbol has a value (X) that is larger than the maximum value detected when generating the coding table information, i = k + 1 is set, the next X ′ is calculated, and X ′ is the number of bits. A code word is obtained by adding 1 ^k (a sequence of k consecutive 1s) to the beginning of the binary representation of L ₀ .
_k
X ′ = X−Σ 2 ^Lj + 1
^{j = 1}
Here, L ₀ is the number of bits necessary to represent the next value.
_k
2 ^L -Σ 2 ^{Lj
j = 1}
Here, L is the symbol bit length.

  The encoding unit 104 outputs the code word encoded as described above. The encoding table information holding unit 805 includes a memory for holding the encoding table information. The encoding table information holding unit 805 transmits the encoding table information to the encoding unit 104 in order to encode a symbol input to the data encoding device 100. The encoding table information generated from the latest W symbols including the symbols input to the data encoding device 100 is received from the cumulative appearance frequency distribution measuring unit 103, overwritten and held.

(Configuration of data decoding device)
Next, the configuration of the data decoding apparatus 200 according to the second embodiment will be described with reference to FIG. The data decoding apparatus 200 includes a decoding unit 201, an encoding table information holding unit 902, a cumulative appearance frequency distribution measuring unit 903, a maximum value detecting unit 904, and a buffer 905.

  The buffer 905 inputs one or more symbols from the encoded symbol sequence transmitted from the data encoding device 100 based on the parameter information transmitted from the data encoding device 100, and inputs the input 1 or 2 This is a memory capable of holding the latest W symbols including two or more symbols. The parameter information indicates a delimiter of symbols to be input for one decoding process in the encoded symbol series.

  The buffer 905 stores the appearance frequency of each symbol value of the latest W symbols. The contents of the buffer 905 are referred to by the maximum value detection unit 904 and the cumulative appearance frequency distribution measurement unit 903. Note that the buffer 905 corresponds to a storage unit of the data decoding device 200.

  The maximum value detection unit 904 detects the symbol having the maximum value among the W symbols in the buffer 905 and outputs the symbol value to the cumulative appearance frequency distribution measurement unit 903.

The cumulative appearance frequency distribution measurement unit 903 observes W symbols in the buffer 905 and uses the maximum value output from the maximum value detection unit 904 to calculate the cumulative appearance frequency distribution from the above A (1) to A (4 ) And finally obtained k and L _i (i = 1, 2,..., K) are output to the encoding table information holding unit 902 as encoding table information.

  The encoding table information holding unit 902 is configured by a memory for holding the encoding table information, and holds the encoding table information transmitted from the data encoding device 100 as an initial value. Thereafter, in order to decode the symbols input to the data decoding apparatus 200, the encoding table information is provided to the decoding unit 201, and the cumulative appearance frequency distribution measurement is performed from the latest W symbols including the decoded symbols. The new encoding table information generated by the unit 903 is overwritten and held.

  The decoding unit 201 receives a sequence in which symbols are encoded, takes out a codeword from the sequence in which symbols are encoded while referring to the encoding table information held in the encoding table information holding unit 902, and corresponding symbols Convert to and output. Specifically, in the following steps C (1) ′ to C (2) ′, a codeword of a portion necessary for symbol decoding is cut out and converted into a symbol.

C (1) ′ When the first bit is 1 ⁽ⁱ⁻¹⁾ 0 (i = 1, 2,..., K), from 1 ⁽ⁱ⁻¹⁾ 0 (i = 1, 2,..., K) The code word length L _i is followed by a part of the code word necessary for symbol decoding, and a numerical value represented as a binary representation is set as X ′. When the first bit is 1 ^k (in this case, i = k + 1), the code word length L ₀ is followed by a code word of a part necessary for symbol decoding, and this is expressed as a binary number. The numerical value represented is X ′. L ₀ is the number of bits necessary to represent the next value. L is the symbol bit length.
_k
2 ^L -Σ 2 ^{Lj
j = 1}

C (2) ′ The next value X is calculated and used as a symbol to be decoded.
_i-1
X = X ′ + Σ 2 ^Lj + 1
^{j = 1}
By such a method, the data decoding apparatus 200 decodes the encoded symbol and outputs a decoded symbol.

  The symbols obtained in this way are output as decoded data (symbols) and are output to the buffer 905 in order to generate encoding table information for decoding the next encoded data. Further, the buffer 905 may store the number of appearances (appearance frequency) of each symbol value of the latest decoded W symbols.

(Operation of Data Encoding Device 100)
Next, compression encoding processing executed by the data encoding device 100 of the present embodiment will be described with reference to the flowchart of FIG. In this description, first, a process after compressing and encoding W symbols (symbols X _{1 to} X _w ) using the coding table information held in the coding table information holding unit 805, In addition to compressing and encoding new symbols input from the outside this time, encoding table information is generated from the W symbols compressed and encoded this time in order to compress and encode new symbols input from the outside next time. Processing will be described.

First, the CPU of the data encoding apparatus 100 starts processing from step S1100, proceeds to step S401, and determines whether there is a symbol to be compression encoded. If there is no symbol to be compressed and encoded, the CPU makes a “No” determination at step S401 to proceed to step S1105 to end the process. If there is a symbol to be compression-encoded, the CPU makes a “Yes” determination at step S 401 to proceed to step S 1101 to input one symbol (symbol X _{w + 1 in} FIG. 10) to the buffer 101 and the encoding unit 104. Then, the process proceeds to step S1102.

Next, in step S1102, the CPU (encoding unit 104) uses the encoding table information held in the encoding table information holding unit 405 for the read symbol Xw _{+ 1} , and the above-described B (2) to B (2) to B (2) ˜. Encoding is performed by the method B (4). However, B (2) is also applied when k = 1.

Further, in the process of B (4), even when i = k, 1 ^(i-1) 0 (1 is continued by ^{i-1) at the} head of the X 'representing the binary representation of L _i bits. A code word is added with 0 added later). If it is a symbol (X) that is larger than the maximum value detected when generating the coding table information, i = k + 1, the next X ′ is calculated, and X ′ is the number of bits L _0. A code word is obtained by adding 1 ^k (k made of 1 consecutive numbers) to the beginning of the binary representation of.
_k
X ′ = X−Σ 2 ^Lj + 1
^{j = 1}
L ₀ is the number of bits necessary to represent the next value.
_k
2 ^L -Σ 2 ^{Lj
j = 1}
Here, L is the symbol bit length.

Next, the CPU proceeds to step S1103 to determine the number of appearances of each of the W symbols X _{2 to} X _{w + 1} held in the buffer 101, and proceeds to step S404 to perform _W symbols X _{2 to} X _{w + 1.} The symbol with the maximum value is detected.

Next, the CPU (cumulative appearance frequency distribution measurement unit 103) proceeds to step S405 and sets k = 1 and C = 0 as initial settings. This corresponds to step A (1) in the configuration explanation of the cumulative appearance frequency distribution measuring unit 103. Next, CPU (cumulative frequency distribution measuring unit 103), the process proceeds to step S406, and accumulates the number of occurrences from the symbol C sequentially accumulated value determined closest symbol X in W / ^{2 k.} This corresponds to step A (2) in the configuration explanation of the cumulative appearance frequency distribution measuring unit 103.

Then, CPU (cumulative frequency distribution measuring unit 103), the process proceeds to step S407, obtains the number of bits _{L k} required to represent the value of (X-C + 1). This corresponds to step A (3) in the configuration explanation of the cumulative appearance frequency distribution measuring unit 103. Next, the CPU (cumulative appearance frequency distribution measuring unit 103) proceeds to step S408, and the maximum value of the symbol detected in step S404 is L _i (i = 1, 2,..., K) calculated in step S407. Range obtained from
_k-1
k
Σ 2 ^Lj to Σ2 ^Lj −1
^{j = 1 j = 1}
It is determined whether it is in. That is, the CPU (cumulative appearance frequency distribution measurement unit 103) determines whether or not the maximum value Cmax satisfies the condition of C ≦ Cmax ≦ C + 2 ^Lk −1. This corresponds to A (4) described above.

At this time, if “No” is determined in step S408, the CPU (cumulative appearance frequency distribution measurement unit 103) proceeds to step S409, increments k by 1, and substitutes the value of C + 2 ^Lk for C. It returns to S406 and repeats the process of step S406-step S409 until it determines with "Yes" in step S408.

On the other hand, if “Yes” is determined in step S408, the CPU (cumulative appearance frequency distribution measurement unit 103) proceeds to step S1104 to calculate the calculated encoding table information k, _Li (i = 1, 2, .., K) are held in the coding table information holding unit 805, and the process returns to step S401. In this way, encoding table information for compressing and encoding symbols input to the data encoding apparatus 100 next time is generated and held.

(Operation of Data Decoding Device 200)
Next, the decompression decoding process executed by the data decoding apparatus 200 of this embodiment will be described with reference to the flowchart of FIG. In this description, first, it is processing after decompression decoding W symbols (symbols X _{1 to} X _w ) using the coding table information held in the coding table information holding unit 902. In order to decompress and decode a new symbol transmitted from the data encoding device 100 and to decompress and decode a new symbol transmitted from the data encoding device 100 next time, the W symbols that have been decompressed and decoded this time are used. A process for generating the encoding table information will be described.

  First, the CPU of the data decoding apparatus 200 starts processing from step S1200, proceeds to step S1201, and determines whether there is encoded data to be decoded. If there is no encoded data to be decoded, the CPU makes a “No” determination at step S1201 to proceed to step S1210, and ends the process.

  On the other hand, if there is encoded data to be decoded, the CPU (decoding unit 201) determines “Yes” in step S1201, proceeds to step S1202, and stores the code held in the coding table information holding unit 902. Using the conversion table information, the symbols encoded by the methods C (1) ′ to C (2) ′ are decoded, and the decoded symbols are output as decoding results, and the decoded symbols are output to the buffer 905. ,Hold.

Next, the CPU proceeds to step S1203, obtains the number of appearances of each of the W symbols X _{2 to} X _{w + 1} held in the buffer 905, proceeds to step S1204, and proceeds to W symbols X _{2 to} X _{w + 1.} The symbol with the maximum value is detected.

Next, the CPU (cumulative appearance frequency distribution measurement unit 903) proceeds to step S1205, and sets k = 1 and C = 0 as initial settings. This corresponds to step A (1) in the configuration explanation of the cumulative appearance frequency distribution measuring unit 903. Next, CPU (cumulative frequency distribution measuring unit 903), the process proceeds to step S1206, in the symbol sequence in the buffer 905 accumulates the frequency of occurrence of the symbol C in order, symbol closest to the accumulated value W / ^{2 k} Find X. This corresponds to step A (2) in the configuration explanation of the cumulative appearance frequency distribution measuring unit 903.

Then, CPU (cumulative frequency distribution measuring unit 903), the process proceeds to step S1207, obtains the number of bits _{L k} required to represent the value of (X-C + 1). This corresponds to step A (3) in the configuration explanation of the cumulative appearance frequency distribution measurement unit 903. Next, the CPU (cumulative appearance frequency distribution measurement unit 903) proceeds to step S1208, and the maximum value detected in step S1204 is calculated from L _i (i = 1, 2,..., K) calculated in step S1207. Obtained range,
_{k-1 k}
Σ 2 ^Lj to Σ2 ^Lj −1
^{j = 1 j = 1}
It is determined whether it is in. That is, the CPU (cumulative appearance frequency distribution measurement unit 903) determines whether or not the maximum value Cmax satisfies the condition of C ≦ Cmax ≦ C + 2 ^Lk −1. This corresponds to A (4) described above.

If “No” is determined in step S1208, the CPU (cumulative appearance frequency distribution measurement unit 903) proceeds to step S1209, increments k by 1, and substitutes the value of C + 2 ^Lk into C, and then proceeds to step S1206. Returning to step S1208, the processes in steps S1206 to S1209 are repeated until “Yes” is determined in step S1208.

On the other hand, if “Yes” is determined in step S1208, the CPU (cumulative appearance frequency distribution measurement unit 903) proceeds to step S1210 to calculate the calculated encoding table information k, L _i (i = 1, 2). ,..., K) are held in the coding table information holding unit 902, and the process returns to step S1201. In this way, encoding table information for decompressing and decoding symbols transmitted from the data encoding device 100 next time is generated and held.

  In the second embodiment, in order to generate encoding table information, the data decoding apparatus 200 has already generated encoding table information from W symbols preceding the symbol to be encoded. Coding table information can be generated from the decoded symbols. Thus, if the data decoding apparatus 200 receives the encoding table information from the data encoding apparatus 100 only once as encoded data, it is not necessary to receive this information from the data encoding apparatus 100 thereafter. As a result, the data encoding apparatus 100 does not have to include the encoding table information in the compressed encoded data, and the overhead is reduced.

(Modification of the second embodiment)
In the second embodiment, as illustrated in FIG. 11, the data encoding apparatus 100 shifts W symbols “one by one” (for example, from symbols X _{1 to} X _w to symbols X _{2 to} X _{w + 1).} And the number of appearances of the symbols in the shifted range is held in the buffer 101, and encoding table information for compressing and encoding new symbols to be transmitted next time is generated from the number of appearances of the held symbols. The information is held in the encoding table information holding unit 805.

In the second embodiment, as illustrated in FIG. 12, the data decoding apparatus 200 shifts W symbols “one by one” (for example, from symbols X _{1 to} X _w to symbols X ₂ to X _{w (} shifted to _{w + 1} ), the symbols in the shifted range and the number of appearances of those symbol values are held in the buffer 905, and a new transmission transmitted from the data encoding device 100 next time is performed from the number of appearances of the held symbol values. Coding table information for decompressing and decoding symbols is generated, and the information is held in the coding table information holding unit 902.

On the other hand, in the modification of the present embodiment, the CPU of the data encoding apparatus 100 inputs W symbols (symbols X _{w + 1 to} X _2w ) in step S1101 in FIG. In this case, the CPU encodes the newly input W symbols in step S1102 and determines the number of appearances of the symbols X _{1 to} X _w and the symbols X _{1 to} X _w held in the buffer 101 as the symbol X. after updating to the number of occurrences of _w + _{1 ~X 2w} and symbol _X w + 1 ~X _2w, using the number of occurrences of W symbols that you entered this time, next time by processing the step S404~ step 409, new input from the outside Encoding table information for compressing and encoding such W symbols is generated, and the generated encoding table information is held in the encoding table information holding unit 805 in step S1104.

In the modification of the present embodiment, the CPU of the data decoding device 200 inputs W symbols (symbols X _{w + 1 to} X _2w ) transmitted from the data encoding device 100, and in step S1202 of FIG. , The W symbols are decoded, and the number of appearances of the symbols X _{1 to} X _w and the symbols X _{1 to} X _w held in the buffer 905 is changed to the number of appearances of the symbols X _{w + 1 to} X _2w and the symbols X _{w + 1 to} X _2w . Then, the new W symbols transmitted from the data encoding device 100 are decompressed and decoded next time by processing steps S1205 to S1209 using the number of appearances of the W symbols input this time. Coding table information is generated, and in step S1210, the generated coding table information holding unit 902 stores the coding table information. Hold.

  As described above, in the modification of the second embodiment, the data encoding device 100 and the data decoding device 200 encode and decode W symbols newly input this time from W symbols input previously. Encoding table information is generated. In this manner, the data decoding apparatus 200 can generate the encoding table information from the already decoded symbols (W symbols input last time). For this reason, once the data decoding apparatus 200 receives the encoding table information as encoded data, it is not necessary to receive this information thereafter. As a result, the encoding table information need not be included in the compressed encoded data, and the overhead is reduced.

(Third embodiment)
In the embodiments described so far, as shown on the left side of FIG. 13, the number of appearances of each symbol value (symbol 0 to symbol 15) of W symbols is determined for each symbol value by the buffer 101 (data encoding device 100) and It was held in the buffer 905 (data decoding apparatus 200).

In the present embodiment, as shown on the right side of FIG. 13, each symbol value is divided every power of 2 (2 ⁱ : i = 0, 1, 2,...) In order from the smallest symbol value. The appearance frequency of each symbol value is accumulated for each delimiter, and the accumulated values are held in the buffer 101 and the buffer 905, respectively.

  Specifically, each symbol value is divided every power of 2, such as symbol 0, symbol 1, symbol 2 to 3, symbol 4 to 7, symbol 8 to 15, and the number of occurrences for symbol 0 and symbol 1 “300” and “200” are held in each buffer. Also, the accumulated value “180” of the appearance numbers of the symbols 2 and 3 is held in each buffer. Further, the accumulated value “180” of the appearance numbers of the symbols 4 to 7 is held in each buffer. Further, the accumulated value “140” of the appearance numbers of the symbols 8 to 15 is held in each buffer.

  According to the present embodiment, it is possible to reduce the memory area in the buffer 101 and the buffer 905 for storing the appearance frequency of the symbol value for each symbol value. In addition, since the number of repetitions of the loop processing performed by the cumulative appearance frequency distribution measuring unit 103 and the cumulative appearance frequency distribution measuring unit 903 is reduced, the load on the CPU can be reduced.

  In the above embodiment, the operations of the respective units are related to each other, and can be replaced as a series of operations in consideration of the relationship between each other. And it can be set as embodiment of method invention by replacing in this way.

  Further, by replacing the operation of each unit with the processing of each unit, the program can be implemented. Further, by storing the program in a computer-readable recording medium in which the program is recorded, an embodiment of a computer-readable recording medium recorded in the program can be obtained.

  Therefore, the embodiment of the data encoding method is a data encoding method for encoding a symbol input from the outside, and calculates the appearance frequency of each symbol of a fixed number of symbols input from the outside, and calculates the above calculation Based on a predetermined cumulative value of the appearance frequency of each symbol and a predetermined target cumulative value, encoding table information that is information related to the codeword length of the codeword in which each symbol is encoded is generated A data encoding program for causing a computer to execute a process for encoding each symbol into a code word using the generated encoding table information, and a computer storing the data encoding program An embodiment of a readable recording medium can be provided.

  The embodiment of the data decoding method is a data decoding method for decoding a codeword in which symbols are encoded, and a fixed number of codewords transmitted from the data encoding device and the codeword length of each codeword. And a process for inputting coding table information, which is information related to the code, and a process for decoding each inputted codeword into each symbol using the inputted coding table information. An embodiment of a data decoding program and a computer-readable recording medium storing the data decoding program can be provided.

  Each processing in the embodiment of the program and the embodiment of the computer-readable recording medium on which the program is recorded is achieved by the computer executing the program.

  As mentioned above, although preferred embodiment of this invention was described referring an accompanying drawing, it cannot be overemphasized that this invention is not limited to the example which concerns. It will be apparent to those skilled in the art that various changes and modifications can be made within the scope of the claims, and these are naturally within the technical scope of the present invention. Understood.

  The present invention can be applied to a data encoding device that generates encoding table information with a reduced amount of information, and a data decoding device that decodes data using the encoding table information.

It is a figure which shows the structure of the data coding apparatus concerning 1st Embodiment of this invention. It is a figure which shows the structure of the data decoding apparatus in the embodiment. It is a figure for demonstrating the symbol sequence input into the data coding apparatus of the embodiment. It is the flowchart which showed the routine which a data coding apparatus performs in the same embodiment. It is the figure which showed the value which each variable has at the time of each loop process which a data coding apparatus performs in the same embodiment. It is the figure which showed the relationship between each codeword corresponding to each symbol and encoding table information in the same embodiment. It is the figure which showed the value of the codeword actually encoded from the symbol using the encoding table information in the same embodiment. It is a figure which shows the structure of the data coding apparatus concerning 2nd Embodiment of this invention. It is a figure which shows the structure of the data decoding apparatus concerning the embodiment. It is a figure for demonstrating the symbol sequence input into the data coding apparatus of the embodiment. It is the flowchart which showed the routine which a data coding apparatus performs in the same embodiment. It is the flowchart which showed the routine which a data decoding apparatus performs in the same embodiment. The table held by the data encoding device and the data decoding device according to the first and second embodiments of the present invention is compared with the table held by the data encoding device and the data decoding device according to the third embodiment of the present invention. FIG.

Explanation of symbols

DESCRIPTION OF SYMBOLS 100 Data encoding apparatus 101 Buffer 102 Maximum value detection part 103 Cumulative appearance frequency distribution measurement part 104 Encoding part 200 Data decoding apparatus 201 Decoding part 805 Encoding table production | generation information holding part 902 Encoding table production | generation information holding part 903 Cumulative appearance frequency Distribution measurement unit 904 Maximum value detection unit 905 Buffer

Claims (11)

A data encoding device for encoding symbols comprising:
Appearance obtained by calculating the appearance frequency of each symbol value of a fixed number of externally input symbols and accumulating the appearance frequency of each symbol value in ascending order from any of the calculated symbol values In order to encode and express the symbol value corresponding to the cumulative value of the appearance frequency when the cumulative value of the frequency is a value smaller than the total number of symbols and the closest value to the target cumulative value which is an arbitrary value A process of obtaining a required number of bits Li, which is a loop process that is repeatedly executed until the number of bits Li required to encode and represent a symbol value for each target cumulative value is obtained; The number of repetitions k and the number of bits Li (i = 1, 2,..., K) obtained by the loop processing are information related to the codeword length of the codeword in which each symbol is encoded. An encoding The cumulative frequency distribution measuring unit for generating a table information;
A data encoding apparatus comprising: an encoding unit that encodes each of the symbols using the generated encoding table information. Said data encoding device, further comprising:
A maximum value detector for detecting a maximum value of a certain number of symbols input from the outside;
The cumulative appearance frequency distribution measurement unit
2. The data encoding apparatus according to claim 1 , wherein the number of bits Li required to encode and represent the maximum value of the detected symbol is obtained. The encoding table information is:
To represent the codeword length which varies for each power of two corresponding to each symbol value, according to claim 1 or claim 2, characterized in that the information generated for each power of two Data encoding device. The encoding unit includes:
The data coding apparatus according to any one of claims 1 to 3, characterized in that respectively encode each symbol by fitting the coding table information in a predetermined condition. The target cumulative value is
The data encoding apparatus according to claim 1 , wherein the data encoding apparatus is a value that decreases each time the loop processing is repeated. Each symbol value is
Zero or more data coding apparatus according to any one of claims 1 to 5, characterized in that a positive value. Said data encoding device, further comprising:
A coding table information holding unit for holding the generated coding table information;
The encoding unit includes:
Wherein one or more symbols to be newly input from the outside to any one of claims 1 to 6, wherein the encoded using an encoding table information stored in the encoding table information holding unit Data encoding apparatus. Said data encoding device, further comprising:
A storage unit for storing the appearance frequency of each symbol value of a certain number of symbols including one or more newly input symbols from the outside this time for each symbol value;
The cumulative appearance frequency distribution measurement unit
Calculating the appearance frequency of each symbol value stored in the storage unit, generating encoding table information based on the calculated cumulative value of the appearance frequency of each symbol value and the target cumulative value;
The encoding table information holding unit is
Holding the generated encoding table information;
The encoding unit includes:
The data according to claim 7 , wherein next time, one or more newly input symbols are encoded using the encoding table information held in the encoding table information holding unit. Encoding device. The number of one or more symbols to be newly input from the outside, data coding apparatus according to claim 7 or claim 8 characterized in that it is a fixed number. The storage unit
Instead of storing the appearance frequency of each symbol value for each symbol value, each symbol value is divided into powers of 2 in order from the smallest symbol value, and the appearance frequency of each symbol value within the division is accumulated for each division. 9. The data encoding apparatus according to claim 8 , wherein the accumulated values are respectively stored. A data encoding method for encoding symbols comprising:
Appearance obtained by calculating the appearance frequency of each symbol value of a fixed number of externally input symbols and accumulating the appearance frequency of each symbol value in ascending order from any of the calculated symbol values When the cumulative value of the frequency is smaller than the total number of symbols and is the closest to the target cumulative value, which is an arbitrary value, to encode and represent the symbol value when having the cumulative value of the appearance frequency Is a loop process that is repeatedly executed until the number of bits Li necessary to encode and represent the symbol value for each target accumulated value is obtained. , The number of repetitions k and the number of bits Li (i = 1, 2,..., K) obtained in each loop processing , information related to the codeword length of the codeword in which each symbol is encoded Encoding The cumulative frequency distribution measuring step of generating a Buru information;
A data encoding method comprising: encoding each of the symbols using the generated encoding table information.

Images