JP2025024868A - Decoder, Encoder, Decoding Method, and Encoding Method - Google Patents

Abstract

To improve compression efficiency of data.SOLUTION: An encoder 10 which encodes encoding target data including a plurality of integer values comprises an encoding section 13 which identifies block data, in which a plurality of integer values is arranged side by side, from among the encoding target data and encodes the block data into a coupled code for which a plurality of alpha codes is coupled with a CBT code. The encoding section 13 may also encode a plurality of kinds of block data into coupled codes for which values of a plurality of alpha codes are equal and values of CBT codes are different.SELECTED DRAWING: Figure 1

Description

The present invention relates to a technology for compressing data.

Conventionally, compression processing has been used to reduce the volume of data. For example, Golomb coding (see, for example, Non-Patent Document 1) is known as a technique for coding integer data strings that follow a geometric distribution with a small amount of code.

In addition, when encoding an information source that is an integer data string, a technique is known in which the information source is expanded to encode an expanded information source in order to improve the encoding efficiency (see, for example, Non-Patent Document 2).

S. W. Golomb, “Run-Length Encodings,” IEEE Transactions on Information Theory, vol. IT-12, no. 3, pp. 399-401, July 1966. Hiroshi Miyagawa, "Information Theory", edited by the Institute of Electrical Communication Engineers, Corona Publishing, 1979

According to Shannon's source coding theorem, the average code length per symbol can be reduced to the entropy of the source. In this way, when reduced to the entropy, the average code length per symbol is often not an integer.

For example, when encoding using Golomb coding, which assigns one code to each symbol, the code length for each symbol cannot be set to anything other than an integer, so the average code length cannot be made as short as possible, and it is often impossible to get close enough to the entropy of the information source.

On the other hand, methods of bringing the amount of code per symbol closer to the entropy include Huffman coding of the extended information source and arithmetic coding, but these methods involve a lot of additional information other than the codes describing each symbol, and as a result, there are cases where compression efficiency cannot be improved.

The present invention has been made in consideration of the above circumstances, and its purpose is to provide a technology that can improve data compression efficiency.

To achieve the above object, an encoder according to one aspect is an encoder that encodes encoding target data that includes multiple integer values, and includes an identification unit that identifies block data containing a series of multiple integer values from the encoding target data, and an encoding unit that encodes the block data into a combined code that combines multiple alpha codes and CBT codes.

The present invention can improve data compression efficiency.

FIG. 1 is a diagram showing the overall configuration of a processing system according to an embodiment. FIG. 2 is a diagram illustrating a first example of Golomb coding. FIG. 3 is a diagram illustrating a second example of Golomb coding. FIG. 4 is a diagram illustrating group numbers according to one embodiment. FIG. 5 is a diagram illustrating symbols belonging to a group with g ₃ =2 according to one embodiment. FIG. 6 is a diagram illustrating a one-dimensional index t _n according to an embodiment. FIG. 7 is a diagram illustrating symbols belonging to a group with g ₃ =2 when m ³ =2 according to an embodiment. FIG. 8 is a diagram showing the relationship between a ₀ , a ₁ , a ₂ and tg′ ₃ according to one embodiment. FIG. 9 is a diagram illustrating a local index _tg'2 according to an embodiment. FIG. 10 is a diagram illustrating a local index _tg'1 according to an embodiment. FIG. 11 is a diagram illustrating index _t'2 when ^m2 =2 according to one embodiment. FIG. 12 is a diagram showing the relationship between a ₀ , a ₁ and t′ ₂ according to one embodiment. FIG. 13 is a diagram showing the relationship between a ₀ , a ₁ and t ₂ according to one embodiment. FIG. 14 is a flowchart of an encoding process according to an embodiment. FIG. 15 is a flowchart of a decoding process according to an embodiment. FIG. 16 is a diagram illustrating an average code length by encoding according to an embodiment. FIG. 17 is a diagram illustrating the configuration of a computer device according to an embodiment.

The following embodiments are described with reference to the drawings. Note that the embodiments described below do not limit the invention as claimed, and not all of the elements and combinations thereof described in the embodiments are necessarily essential to the solution of the invention.

First, we will explain the processing system according to one embodiment.

Figure 1 is an overall configuration diagram of a processing system according to one embodiment.

The processing system 1 includes an encoder 10 and a decoder 30. The encoder 10 and the decoder 30 are connected via a network 50. The network 50 is, for example, a Local Area Network (LAN) or a Wide Area Network (WAN).

The encoder 10 includes a target data input unit 11, a prediction difference calculation unit 12, an encoding unit 13, and a compressed data output unit 14. Here, the encoding unit 13 is an example of a determination unit, and the compressed data output unit 14 is an example of a transmission unit.

The target data input unit 11 inputs data to be compressed. The target data may be, for example, audio data converted by PCM (Pulse Code Modulation). The target data may be obtained from the auxiliary storage device 106 (see FIG. 17) in the encoder 10, or may be obtained from a recording device (not shown).

The prediction difference calculation unit 12 performs a process of calculating a prediction difference for each data element (data at a specified point in time) of the audio data. An example of the process of calculating the prediction difference is described below.

Here, the data string of the audio data is denoted by x[t], where t=0, 1, 2, . . . , n-1, and x[t] is an integer.
When the prediction difference x′[t] of x[t] is predicted using the previous data x[t−1], the prediction difference x′[t] can be expressed as shown in the following equation (1).

The encoding unit 13 converts the prediction difference x′[t] calculated by the prediction difference calculation unit 12 into conversion target data p[t] (data to be processed) to be encoded, using the following equation (2).
p[t]=g(x'[t])...(2)
Here, g( ) is a function that maps positive and negative integers to non-negative integers, and can be expressed as shown in equation (3).

The encoding unit 13 generates a blocked time series p ⁿ [t] shown in the following equation (4) by blocking each value of p[t] in units of n.
p ⁿ [t] = (p[nt]p[nt+1]...p[nt+n-1])...(4)

Next, the encoding unit 13 performs the encoding according to this embodiment shown below on p ⁿ [t] (data to be encoded). Note that the encoding according to this embodiment uses encoding similar to Golomb encoding as described later, and the encoding unit 13 determines a parameter m ⁿ in the encoding. The parameter m ⁿ may be estimated based on the average value of p [t], for example, or the value of the parameter m ⁿ may be changed to actually perform encoding and search for a parameter with the highest encoding efficiency.

Next, we will explain the encoding process according to this embodiment.

In this embodiment, the data sequence output from an information source S that outputs data having a stationary distribution that follows a geometric distribution is the target for encoding. Here, the probability mass function for element i of the data sequence can be expressed as shown in the following formula (5).

Here, θ means the probability that P[i] outputs something other than 0, and 0<θ<1.

In this embodiment, an n-th order extended information source S ⁿ is considered, which outputs blocks obtained by dividing a data sequence output from an information source S into n blocks, and each block output from the extended information source S ⁿ is treated as a symbol to be coded.

For example, if the data string output from the information source S is {0, 1, 0, 0, 2, 3, 0, 0, 1, 0, 2, 1, 0, 0}, the symbols output from the extended information source ^S2 will be {01, 00, 23, 00, 10, 21, 00}.

Here, let us consider the occurrence probability (appearance probability) of each symbol output from the extended information source ^S2 .
First, according to equation (5), the probability that the information source S generates the symbol "0" is (1-θ). Also, the probability of generating the symbol "0" followed by the symbol "0" is (1-θ) ^2. Similarly, the probability of generating the symbol "1" followed by the symbol "0" is (1-θ) ² θ.
Therefore, the probability P(i ₀ )P(i ₁ ) that the information source S generates the symbol "i ₁ " following the symbol "i ₀ " can be expressed as shown in the following equation (6).

The occurrence probability P(i ₀ )P(i ₁ ) is the same as the occurrence probability P(i ₀ i ₁ ) that the extended information source S ² generates the symbol “i ₀ i ₁ ”.
Furthermore, by generalizing equation (6), the occurrence probability P(i ₀ , i ₁ , ..., i _n-1 ) of generating a symbol output from the n-th order extended information source S ⁿ can be expressed as shown in the following equation (7).

For example, when θ=1/2, the code length of each symbol output from the information source S is an integer when the symbol is most efficiently encoded by Golomb encoding. In this case, when applied to the symbol "i ₀ i ₁ " output from the extended information source S ² , the symbols i ₀ and i ₁ are each encoded with the Golomb parameter m=1, and the amount of code remains the same, allowing most efficient encoding. Here, the Golomb code with m=1 in Golomb encoding is the alpha code itself, without the CBT code. That is, it is a combination of the alpha code for i ₀ and the alpha code for i ₁ .

By the way, Golomb coding can be seen as a coding method that combines alpha coding and CBT coding, and it can be interpreted that the geometric distribution corresponding to θ = 1/2 is expressed in the alpha coding part, and the effective θ is set by stretching this by m times using the CBT coding.

Here, we explain Golomb coding using diagrams.

Figure 2 is a diagram for explaining a first example of Golomb coding. Figure 3 is a diagram for explaining a second example of Golomb coding. Figure 2 shows Golomb coding that is optimal when the Golomb parameter m = 1, and Figure 3 shows Golomb coding that is optimal when the Golomb parameter m = 2. In Figures 2 and 3, rectangles indicate symbols, and the numbers in the rectangles indicating each symbol indicate the symbol number. In addition, below the rectangles, the alpha code and CBT code when the symbol is coded are shown. In addition, the numbers (1/2) on the arrows between the rectangles indicate the relationship of occurrence probability between symbols (symbol groups).

When m=1, as shown in Figure 2, the codes for the symbols are only alpha codes, there are no CBT codes, and symbol 0 is coded as "1", symbol 1 as "01", symbol 2 as "001", and so on. In this case, it indicates that the probability of occurrence of the right-hand symbol is 1/2 compared to the left-hand symbol.

When m=2, as shown in Figure 3, the code for the symbols is a code that includes one alpha code and a CBT code, and symbol 0 is encoded as "10", symbol 1 is encoded as "11", symbol 2 is encoded as "010", and so on.

When m = 1, the occurrence probability is 1/2 for every symbol, which corresponds to θ = 1/2 according to equation (5). When m = 2, the occurrence probability is 1/2 for every two symbols, which corresponds to θ = √(1/2) according to equation (5) (in this specification, this notation indicates that √ is crossed over 1/2).

In this embodiment, the Golomb coding method is developed so that each symbol output from the extended information source ^S2 is coded by a combined code that combines a plurality of alpha codes and a CBT code.

Here, as described above, when θ=1/2, in order to efficiently encode the symbol "i ₀ i ₁ ", it is sufficient to add the alpha code for i ₁ following the alpha code for i _0. By expressing the symbol as a combined code of alpha code + alpha code + CBT code, which is obtained by combining this code with a CBT code, it is possible to realize encoding suitable for θ larger than 1/2.

If the type of input to be coded by the CBT code is ^m2 , then when ^m2 =1, the CBT code is not necessary, and θ=1/2. When ^m2 =2, this means that the entire P( _i0 )P( _i1 ) in formula (6) is stretched twice, so the expansion rate in the direction of the probability variable of the probability mass function for each of the symbols " _i0 " and " _i1 " when θ of P( _i0 ) and P( _i1 ) is the same is √(2) times. Therefore, this coding can realize coding suitable for the geometric distribution of θ=2 ^-1/√(2) . Therefore, when generalized with the parameter ^m2 , this coding can realize coding suitable for the geometric distribution of θ=2 ^-1/m .

[Encoding of output data (symbols) from extended information source S ⁿ ]
The following describes the procedure (steps E1 to E8) of encoding by the encoding unit 13 when the nth order symbol "i ₀ i ₁ i ₂ ...i _n-1 " is the target to be encoded and a parameter m ⁿ is given. In this embodiment, the encoding unit 13 determines the values of multiple alpha codes to be assigned to symbols based on the occurrence probability of a sequence of multiple integer values of the nth order symbol, for example, by the following procedure. At this time, the encoding unit 13 performs encoding such that the multiple alpha codes assigned to symbols with a high occurrence probability tend to be shorter. The encoding unit 13 may also perform encoding such that the CBT codes assigned to symbols with a high occurrence probability are shorter.

[Step E1]
The encoding unit 13 obtains a one-dimensional index _tn of the symbol to be encoded (referred to as the target symbol in the description of this process) from _i0 , _i1 , _i2 , ..., _in-1 . Here, the one-dimensional index _tn is the order of the target symbol when all symbols that can be used as symbols of block data are sorted in descending order of probability calculated by a model based on the probability mass function shown in equation (7).

An example of a method for calculating the one-dimensional index t _n will be described below. First, let Σ _k=0 ^n-1 i _k =g _n , where g _n denotes a group. η _n (g _n ), which indicates the minimum value of the one-dimensional index t _n among symbols with the same g _n , can be expressed as shown in the following formula (8). The derivation of formula (8) will be described later.

Here, Π is the symbol for multiplication.

For example, when n=1 to 4, η _n (g _n ) can be expanded as shown in the following equations (9) to (12).

Here, symbols with the same g _n are referred to as symbols belonging to g _n . According to formula (7), symbols belonging to the same g _n appear with the same probability. Therefore, even if the information on the number of a symbol in g _n is determined by any method, the probability of appearance decreases as the one-dimensional index t _n increases. However, in order to ensure that decoding can be performed, it is necessary to make it possible to uniquely identify the symbol between the encoder and the decoder.
For example, the ordinal number of a symbol in g _n can be identified from i ₀ , i ₁ , i ₂ , ..., i _n-2 , and since the degree is reduced by one, the index t _n-1 for g _n-1 can be used as is.

As a specific example, _g3 for " _i0 , _i1 , _i2 " in the extended information source ^S3 is the numerical value written in the rectangle in FIG. 4(C). Here, if we focus only on the symbol with _g3 =2, it will be as shown in FIG. 5. Referring to FIG. 5, it can be seen that for each symbol, even if any one of _i0 , _i1 , and _i2 is missing, the symbol can be identified. Therefore, the symbol can be identified using _i0 and _i1 . Furthermore, a method of making _i0 and _i1 into a one-dimensional index is to calculate a one-dimensional index _t2 and repeat the same calculation, and by repeatedly calculating the one-dimensional index of the dimension one level lower, the one-dimensional index of each symbol can be calculated.
When the index t _n is determined in this manner, the one-dimensional index t _n can be expressed as the sum of η _n (g _n ) in equation (8) and the index t _n-1 for g _n-1 , as shown in equation (13).

Here, t ₀ =0.
According to formula (13), when n = 1, 2, or 3, it can be expressed as shown in the following formulas (14) to (16). In other words, formula (13) can be expressed as shown in the following formula (17).

The values of the one-dimensional indexes _t1 , t2, and ^t3 calculated by formula (17) for each of _the information sources ^S1 , ^S2 , and _S3 can be expressed as shown in FIG. 6. For example, in the case of the expanded information source ^S2 , according to formula (6), the occurrence probability is determined by _i0 + _i1 , and the larger _i0 +i1 is, the lower the occurrence probability is. Therefore, when considering a two-variable plane of _i0 and _i1 , the larger the Manhattan distance from the origin is, the more the occurrence probability monotonically decreases. Therefore, if the indexes are determined in order of occurrence probability, the one-dimensional index _t2 will be as shown in FIG. 6(B).

[Step E2]
The encoding unit 13 obtains index _t'n when encoding with n alpha codes. Note that encoding with n alpha codes corresponds to encoding each symbol when θ=1/2. Here, index _t'n is a quantized value of index _tn as shown in the following equation (18).

[Step E3]
The encoding unit 13 obtains an index _g'n of the group of indexes _t'n .
Specifically, first, the calculation is performed inversely to that for finding the smallest index _tn belonging to the group in equation (8). That is, when n=2, solve g^'n in the following equation (19), when n=3, in the following equation (20), and when n=4, in the following equation ( ₂₁ ), and select a solution that is zero or a positive number. The same applies when n is other than 2, 3, or 4.

Here, _g'n is the minimum value of index _t'n belonging to g^' _n , and is an integer value, so _g'n can be calculated by truncating the decimal portion from g^' _n .

For example, when n=2, g′ _n can be calculated by the following formula (22) based on formula (19), when n=3, g′ n can be calculated by the following formula (23) based on formula (20), and when n=4, g′ n can be calculated by the following formula (24) based on formula (21).

Note that _g'n may be calculated by a method other than the above. For example, it may be calculated by a numerical calculation method capable of finding a solution to a high-order algebraic equation, or the corresponding _g'n may be found by counting up the index _t'n , or a table of the correspondence between _t'n and _g'n may be prepared in advance and found based on the table.

[Step E4]
The encoding unit 13 obtains a sequence number _tg which indicates the ordinal number of the symbol that the index _tn is in the group _g'n .

For example, the minimum index of the group of _g'n is found by a calculation similar to that of equation (8), and the minimum index is multiplied by ^mn to restore it to a value of the same scale as _tn , and this value is subtracted from the index _tn . Specifically, the calculation is performed by the following equation (25).

t _g =t _n -η _n (g' _n )m ⁿ ...(25)

[Step E5]
The encoding unit 13 calculates the type number s of the CBT code in the group _g'n by the following equation (26).

Here, the group _g'n contains (η _n-1 (g' _n +1))m ⁿ symbols using the minimum index number of the next smaller n, so 0≦s<m ⁿ . FIG. 7 is a diagram showing symbols belonging to the group g' ₃ =2 when m ³ =2. As shown in FIG. 7, it can be seen that (η _n-1 (g' _n +1))m ⁿ = (η _3-1 (2+1))2 = 12 symbols (indicated by circles in the diagram) are contained.

[Step E6]
The encoding unit 13 calculates an index t _g'n within the group of _g'n by the following equation (27).

t _g'n =t _g mod (η _n-1 (g' _n +1)) ... (27)
Here, mod indicates a modulus operation, and the index t _g'n satisfies 0≦t _g'n <(η _n-1 (g' _n +1)).

[Step E7]
The encoding unit 13 determines a ₀ , a ₁ , . . . , a _n-1 , which are inputs when converting the index t _g'n into an alpha code.
In this embodiment, since all symbols in the _g'n group have the same probability, _a0 , _a1 , ..., an _-1 only need to satisfy Σk _=0n ^-1a _k = _g'n and be able to uniquely identify the symbols in the group. For example, the method of determining _a0 , _a1 , ..., _an-1 when the symbols are arranged in the order according to _tg'n = Σk ₌ ^1nηk _{( g'k} ) is shown below.
First, a local index tg' _n-1 in the group g'k containing the index t _g'n is calculated by the following formula (28).

tg' _n-1 = tg' _n -η _n (g' _k )...(28)

Next, the group g' _n-1 containing the index t g' n- ₁ is calculated in the same manner as in step E3. That is, g^' _n-1 is found by solving the following equation (29), and g' _n-1 is calculated by truncating the decimal part. Here, from among the solutions obtained by solving equation (29), a solution that is zero or a positive number is selected as g' _n-1 .

Next, a _n-1 is calculated by the following formula (30).

a _n-1 = g' _n - g' _n-1 ...(30)

a _n-1 can be identified as being offset from the maximum value g' _n by the number of local groups g' _n-1 .

By repeating the same process, a _n-2 , . . . a ₁ are specified, and a ₀ is set as shown in the following formula (31).

a ₀ = g' ₁ = t _g'1 ...(31)

This makes it possible to determine all of a ₀ , a ₁ , . . . , a _n-1 .

Here, an example of determining a ₀ , a ₁ , and a ₂ when encoding the symbol of S ³ and the group g′ ₃ =3 and the index t _g′3 =18 will be described.

When group _g'3 = 3, the relationship between _a0 , _a1 , _a2 and _tg'3 is as shown in Fig. 8. From this diagram, it can be seen that index _tg'3 = 18 is ( _a0 , _a1 , _a2 ) = (2, 1, 0). The relationship diagram shown in Fig. 8 can be created, for example, by arranging index _tg'n in order and counting up, so when n or _tg'n is small, a relationship diagram like that shown in Fig. 8 can be created and ( _a0 , _a1 , _a2 ) can be determined based on this diagram.
An example in which (a ₀ , a ₁ , a ₂ ) is determined by calculation rather than from a relationship diagram will be described below.

The index t _g'3 included in the group _g'3 is 10, 11, 12, ..., 19 as shown in Figure 9, and the local index t _g'2 can be calculated as "8" as shown in the following equation (32) using equation (28), and can be expressed as shown in Figure 9.

Next, the group _g'2 including the symbol with index t _g'2 being 8 is calculated as "3" according to equation (22), as shown in the following equation (33).

As a result, _a2 can be calculated from equation (30) as shown in the following equation (34).

a ₂ = g' ₃ - g' ₂ = 0 (34)

Next, the indexes t _g'2 included in the group g' ₂ =3 are 6, 7, 8, and 9 as shown in FIG. 10, and the local index t _g'2 can be calculated as "2" according to equation (28) as shown in equation (35) below, and can be expressed as shown in FIG. 10.

Next, the group g′ ₁ including the symbol with index t _{g′ 1} being 2 is calculated as shown in the following equation (36).

g' ₁ = tg' ₁ = 2 (36)

As a result, _a1 can be calculated from equation (30) as shown in the following equation (37).

a ₁ = g' ₂ - g' ₁ = 1 (37)

Finally, a ₀ can be calculated from equation (31) as shown in the following equation (38).

a ₀ = g' ₁ = 2 (38)

This results in (a ₀ , a ₁ , a ₂ )=(2, 1, 0).

[Step E8]
The encoding unit 13 sequentially encodes each of a ₀ , a ₁ , ..., a _n-1 obtained in step E7 into an alpha code to obtain n alpha codes, and then performs CBT encoding for m ⁿ symbols on the type number s to calculate a CBT code, and creates a combined code by combining the n alpha codes and the CBT code. This makes it possible to encode one of the n-th order blocks output from the extended information source S ⁿ into a combined code.

This allows multiple alpha codes assigned to n-th order symbols to be coded so that they are shorter, and allows the CBT codes assigned to symbols with a high probability of occurrence to be shorter.

[Derivation of Equation (8)]
Here, the derivation of equation (8) will be explained.

When n=1, the number of symbols belonging to _g1 is always 1, as shown by ^S1 in Figure 4, so the minimum value _η1 ( _g1 ) of the one-dimensional index _t1 in the group can be expressed as shown in the following equation (39).

Furthermore, when n = 2, as shown in ^S2 in Figure 4, the number of each group is the sum of numbers that change from 0, 1, 2, ..., so the minimum value _η2 ( _g2 ) of the one-dimensional index _t2 in the group can be expressed as shown in the following equation (40).

Furthermore, when n=3, as shown in ^S3 in FIG. 4, the numbers in each group are the sum of the numbers that change as 0, 3, 6, 10, ..., which means taking the sum for _g2 in ^S2. Therefore, the minimum value _η3 ( _g3 ) of the one-dimensional index _t3 in the group can be expressed as shown in the following equation (41).

In this way, the minimum value η _n (g _n ) of the one-dimensional index t _n in the group for n is recursively found from the number of each group in the case of the next lower degree, leading to equation (8).

[Encoding of output data from the augmented information source ^S2 ]
In the above example, the encoding of the extended information source S ⁿ has been described, but to facilitate understanding, the encoding of the extended information source S ² will be described. Specifically, the encoding procedure (steps E1 to E8) by the encoding unit 13 will be described when the secondary symbol "i ₀ i ₁ " is to be encoded and a parameter m ² is given.

[Step E1]
The encoding unit 13 obtains a one-dimensional index _t2 of the symbol to be encoded (referred to as a target symbol in the explanation of this process) from _i0 , _i1 .

First, let _i0 + _i1 = _g2 . _g2 denotes a group. _η2 (g2), which indicates the minimum value of the one-dimensional index _t2 among the symbols belonging to _g2 , can be expressed as shown in the above formula ( ₁₀ ). In addition, taking into account the order of the symbols in the group _g2 , it can be expressed as shown in the following formula (42).

[Step E2]
The encoding unit 13 obtains index _t'2 when encoding with two alpha codes. Note that encoding with two alpha codes corresponds to encoding each symbol when θ=1/2. Here, index _t'2 is a quantized value of index _t2 as shown in the following equation (43).

For example, when index t ₂ is as shown in FIG. 6, if m ² =2, index t′ ₂ becomes as shown in FIG.

[Step E3]
The encoding unit 13 obtains a group _g'2 of the index _t'2 .
Specifically, first, the calculation is performed inversely to that for finding the minimum index _t2 belonging to the group in equation (10). That is, in equation (19), g^' ₂ is solved and a solution that satisfies g^' ₂ ≧0 is selected. Here, _g'2 is the minimum value of index _t'2 belonging to g^' ₂ and is an integer value, so g'2 can be calculated by truncating the decimal portion from g^ _{' 2} .

Therefore, _g'2 can be calculated by equation (22).

[Step E4]
The encoding unit 13 obtains a sequence number _tg which indicates the ordinal number of the symbol that the index _t2 is in the group _g'n .

For example, the minimum index of the group of _g'n is found by a calculation similar to that of equation (10), and the minimum index is multiplied by ^m2 to restore it to a value of the same scale as _t2 , and this value is subtracted from index _t2 . Specifically, the calculation is performed by the following equation (44).

[Step E5]
The encoding unit 13 calculates the type number s of the CBT code in the group _g′2 by the following equation (45).

Here, the group _g'2 contains ( _g2 +1) ^m2 symbols, so that 0≦s< ^m2 .

[Step E6]
The encoding unit 13 calculates an index t _g'2 within the group of _g'2 by the following equation (46).

t _g'2 = t _g mod (g' ₂ +1) ... (46)
Here, mod indicates a modulus operation, and the index t _g'2 satisfies 0≦t _g'2 <(g' ₂ +1).

[Step E7]
The encoding unit 13 determines a ₀ and a ₁ which are inputs when converting the index t _g′2 into an alpha code.
In this embodiment, since the probabilities of all symbols in group _g'2 are equal, it is sufficient that _a0 + _a1 = _g'2 is satisfied and the symbols in the group can be uniquely identified. For example, _a0 and _a1 may be determined by the following equations (47) and (48).

a ₀ =t _g'1 ...(47)
a ₁ = g' ₂ -t _g'1 ...(48)

[Step E8]
The encoding unit 13 sequentially encodes _a0 and _a1 obtained in step E7 into alpha codes to obtain two alpha codes, and then performs CBT encoding for ^m2 symbols on the type number s to calculate a CBT code, and creates a combined code by combining the two alpha codes and the CBT code. This makes it possible to encode one of the secondary blocks output from the extended information source ^S2 into a combined code.

According to the above-mentioned encoding process, for a symbol represented by index _t2 as shown in FIG. 6, ( _a0 , _a1 ) as shown in FIG. 13 is determined. Here, for a plurality of types of symbols determined to be the same ( _a0 , a1 _{, ...} ), they may be encoded into CBT codes of different lengths (for example, when ^m2 is not a power of 2). For example, when ^m2 = 3, the lengths of the CBT codes are different in binary format, such as 0, 10, and 11. In this embodiment, since ( _a0 , _a1 , ...) is determined for index _tn as shown in FIG. 13, for example, for symbols belonging to the same group, the lengths of a plurality of alpha codes can be made the same, and among them, symbols with small indices (with the same or high occurrence probability) can be encoded into the shortest possible CBT code. Therefore, symbols with small indices can be made into shorter combined codes, and compression efficiency can be improved.

[Encoding of output data from extended information source ^S2 : When the code length of the CBT code is not taken into consideration]
In the above example, for symbols belonging to the same group, processing was performed so that symbols with smaller indexes (with the same or higher occurrence probability) could be encoded into shorter CBT codes, but for symbols belonging to the same group, the length of the CBT code may not be taken into consideration. Even in this case, the length of the multiple alpha codes can be made shorter for symbols with higher occurrence probability, improving compression efficiency.

The following describes the coding of the extended information source ^S2 when the code length of the CBT code is not taken into consideration. Specifically, the coding procedure (steps E1' to E6 _' ) by the coding unit 13 when the second-order symbol " _i0i1 " is to be coded and the parameter ^m2 is given will be described.

[Step E1′]
The encoding unit 13 executes the same process as in step E1.
[Step E2′]
The encoding unit 13 executes the same process as in step E2.
[Step E3′]
The encoding unit 13 executes the same process as in step E3.

[Step E4′]
The encoding unit 13 determines a ₀ and a ₁ which are inputs when converting the index t' ₂ into an alpha code.
In this embodiment, since the probabilities of all symbols in group _g'2 are equal, it is sufficient that _a0 + _a1 = _g'2 is satisfied and the symbols in the group can be uniquely identified. For example, _a0 and _a1 may be determined by the following equations (49) and (50).

a ₀ =t' ₂ ...(49)
a ₁ = g' ₂ - t' ₂ ...(50)

In this example, according to equations (49) and (50), a ₀ and a ₁ are determined for index t' ₂ as shown in FIG.

[Step E5′]
The encoding unit 13 calculates a CBT code type number s _m2 for identifying symbols encoded to the same (a ₀ , a ₁ ). The identification number S _m2 is calculated by the following equation (51).

s _m2 = t mod m ² (51)

[Step E6′]
The encoding unit 13 sequentially encodes _a0 and _a1 obtained in step E5' into alpha codes to obtain two alpha codes, and then performs CBT encoding for ^m2 symbols on the type number _sm2 to calculate a CBT code, and creates a combined code by combining the two alpha codes and the CBT code. This makes it possible to encode one of the secondary blocks output from the extended information source ^S2 into a combined code. This encoding of the extended information source ^S2 without taking into account the code length of the CBT code can simplify the processing compared to the case where the code length of the CBT code is taken into account.

Returning to the explanation of Fig. 1, the compressed data output unit 14 creates compressed data (encoded data) in a file format that combines the combined code obtained by encoding each block (symbol) and the parameter m ⁿ indicating the number of types of CBT codes, and outputs the data to the decoder 30. Here, the parameter m ⁿ may be set in the header portion of the combined code of each block.

The decoder 30 has a compressed data input unit 31, an encoding/decoding unit 32, a target data calculation unit 33, and a target data processing unit 34. Here, the compressed data input unit 21 is an example of a reception unit, and the encoding/decoding unit 32 is an example of a decoding unit.

The compressed data input unit 31 inputs compressed data (data to be processed) transmitted from the encoder 10 via the network 50.

The codec 32 performs the decoding according to this embodiment, which will be described below, on the combined code for each block (symbol) included in the compressed data, using parameters m ⁿ corresponding to this symbol.

Next, we will explain the decoding process according to this embodiment.

Decoding of a joint code in which n-th symbol is encoded
The following describes the procedure (steps D1 to D6) of decoding by the code-decoding unit 32 when a combined code in which n-th order symbols "i ₀ i ₁ i ₂ ...i _n-1 " are encoded is to be decoded and a parameter m ⁿ is given.

[Step D1]
The code decoder 32 decodes the combined code including the n alpha codes and the CBT code to obtain a ₀ , a ₁ , . . . , a _n-1 , and s.

[Step D2]
The codec 32 calculates each local group {g' ₁ , g' ₂ , . . . , g' _n } of the group corresponding to θ=½ by using the following equation (52).

{g' ₁ , g' ₂ ,..., g' _n }={a ₀ , Σ _k=0 ^2-1 a _k ,..., Σ _k=0 ^n-1 a _k }
...(52)

[Step D3]
The codec 32 calculates an index t _g'n corresponding to θ=1/2 in the group of _g'n by the following equation (53).

t _g'n =Σ _k=1 ⁿ η _k (g' _k )...(53)

[Step D4]
The codec 32 calculates a sequence number _tg , which indicates the ordinal number of the symbol to be decoded within the group _g'n , using equation (54).

t _g = s (η _n-1 (g _n +1)) + t _g'n ... (54)

[Step D5]
The codec 32 calculates the index _tn of the symbol to be decoded based on equation (25).

[Step D6]
The codec 32 restores i ₀ , i ₁ , i ₂ , . . . , i _n-1 from the index t _n of the symbol to be decoded by the following process.
First, the coder/decoder 32 finds g^ _n by performing the same calculation as in equation (29), that is, by solving the following equation (55), and calculates g _n by truncating the decimal part.

Next, the codec 32 calculates a local index t _n-1 in the group g _n by the following equation (56).

t _n-1 = t _n -η _n (g _n )...(56)

Next, the coder/decoder 32 calculates the group g _n-1 to which the index t _gn-1 belongs, using equation (57), which is similar to equation (30).

i _n-1 = g _n - _{g n-1} (57)

Next, the coder/decoder 32 calculates i _n-2 , ..., i ₁ by repeatedly using the relational expression (57), and for i ₀ , it sets i ₀ = g ₁ = t _1. This makes it possible to restore the n-th order symbols (i ₀ i ₁ i ₂ ...i _n-1 ). This makes it possible to obtain each symbol, that is, the blocked time series p ⁿ [t].

Decoding of Secondary Symbol-Encoded Joint Codes
The following describes the procedure (steps D1 to D6) of decoding by the code-decoder 32 when the combined code obtained by encoding the secondary symbol "i ₀ i ₁ " is to be decoded and the parameter m ² is given.

[Step D1]
The code decoder 32 decodes the combined code including the two alpha codes and the CBT code to obtain a ₀ , a ₁ , and s.

[Step D2]
The codec 32 calculates each local group _g'2 of the group corresponding to θ=1/2 by the following equation (58).

g' ₂ = a ₀ + a ₁ ... (58)

[Step D3]
The codec 32 sets the index t _g'1 corresponding to θ=1/2 in the group _g'2 as a ₀ .

[Step D4]
The codec 32 calculates the sequence number _tg , which indicates the ordinal number of the symbol to be decoded within the group _g'2 , using equation (59).

t _g =s(g _n +1)+tg' ₁ ...(59)

[Step D5]
The codec 32 calculates the index _t2 of the symbol to be decoded based on equation (44).

[Step D6]
The codec 32 restores i ₀ and i ₁ from the index t ₂ of the symbol to be decoded by the following process.
First, the coder/decoder 32 calculates _g2 by the same calculation as in equation (22), that is, by solving the following equation (60).

Next, the coder/decoder 32 calculates _i0 using the relationship in equation (42).

Next, the codec 32 calculates i ₁ from the relationship i ₀ +i ₁ =g _2. This makes it possible to restore the second-order symbol (i ₀ i ₁ ). This makes it possible to obtain each symbol, i.e., the blocked time series p ² [t].

Returning to the explanation of Figure 1, the target data calculation unit 33 calculates a prediction difference x ^' [t] for each of the conversion target data p[t] obtained by dividing the values of each element of the n-th order symbol of the blocked time series pn[t], by performing an inverse mapping of the process of mapping positive and negative integers to non-negative integers using equation (3) below, i.e., a process of converting the non-negative integers back to the original positive and negative integers, using equation (60) below.
x'[t]=g ^- (p[t]) ...(60)
Here, g ⁻ ( ) is a function that converts a non-negative integer into a positive or negative integer, and can be expressed as shown in equation (61).

The target data calculation unit 33 performs the process shown in equation (62) on the predicted difference x'[t] to restore the data string x[t] of the audio data and create the original audio data (data to be compressed).

The target data processing unit 34 outputs audio by processing the created audio data.

Next, we will explain the processing operations in processing system 1.

First, we will explain the encoding process performed by the encoder 10.

Figure 14 is a flowchart of the encoding process according to one embodiment.

In the encoding process, first, the target data input unit 11 accepts the audio data to be encoded (S11).

Next, the prediction difference calculation unit 12 performs a process of calculating the prediction difference x'[t] for each data element (data at each point in time) of the audio data (S12).

Next, the encoding unit 13 converts the prediction difference x'[t] calculated by the prediction difference calculation unit 12 into conversion target data p[t] (data to be processed) to be encoded, and generates a blocked time series ^pn [t] by blocking each value of the conversion target data p[t] in units of n (S13).

Next, the encoding unit 13 estimates (determines) parameters m and ⁿ for the CBT code (S14).

Next, the encoding unit 13 performs an encoding process of encoding each block of the blocked time series p ⁿ [t] into a combined code in accordance with the estimated parameters m ⁿ (S15).

Next, the compressed data output unit 14 creates compressed data that combines the combined code obtained by encoding all the blocks and the parameters m and ⁿ of the encoding process, and outputs (transmits) the compressed data to the decoder 30.

This encoding process can shorten the code length when encoding audio data, improving the compression efficiency of the audio data.

Next, we will explain the decoding process performed by the decoder 30.

Figure 15 is a flowchart of the decoding process according to one embodiment.

The compressed data input unit 31 inputs compressed data (an example of data to be processed) transmitted from the encoder 10 via the network 50 (step S31).

Next, the coder/decoder 32 performs a decoding process on each combined code included in the compressed data using the corresponding parameter ^mn to obtain the data before encoding, i.e., the blocked time series ^pn [t], and divides the values of the n elements included in each block of the blocked time series ^pn [t] to obtain the data to be converted p[t] (S32).

Next, the target data calculation unit 33 converts each element of the conversion target data p[t] into a prediction difference x'[t], and restores each element of the prediction difference x'[t] to the original data sequence x[t] (S33).

Next, the target data calculation unit 33 puts all the data strings x[t] together to create voice data, and the target data processing unit 34 performs voice output processing using the created voice data (S34), and the process ends.

The above-mentioned decoding process allows appropriate audio output based on the compressed data created by the encoder 10.

Next, we will explain the average code length of the combined code generated by the above encoding.

Fig. 16 is a diagram for explaining the average code length by the encoding according to an embodiment. Fig. 16(A) shows the parameter ^m2 used in the encoding of this embodiment, the average code length of the combined code obtained by encoding, and the average code length of the code obtained by Golomb encoding in each case where the parameter m= ¹ , 2, 3 is set, when the geometric distribution θ of the extended information source ^S2 is changed, Fig. 16(B) shows the average code length in each encoding when the geometric distribution θ of the extended information source S3 is changed, and Fig. 16(C) shows the average code length in each encoding when the geometric distribution θ of the extended information source ^S4 is changed.

For example, as shown in FIG. 16A, for an extended information source ^S2 that follows a geometric distribution with θ=2−1 ^/√(5) , the average code length of the combined code when ^m2 =5 in the encoding of this embodiment is 3.154 [bits], whereas the average code lengths of the codes by Golomb encoding when m=1, 2, and 3 are 3.753, 3.164, and 3.211 [bits], respectively.

For the extended information source ^S2 , as shown in FIG. 16A, when θ is 2−1 ^/2 , the average code length of the combined code of this embodiment is the same as the average code length of the code by Golomb coding when m=2, but otherwise can be made shorter than the average code length of any code by Golomb coding, thereby improving the data compression efficiency.

Furthermore, for the extended information source ^S3 , as shown in FIG. 16(B), the average code length of the combined code of this embodiment can be made shorter than the average code length of any code based on Golomb coding, thereby improving the data compression efficiency.

Furthermore, for the extended information source ^S4 , as shown in FIG. 16(C), the average code length of the combined code of this embodiment can be made shorter than the average code length of any code based on Golomb coding, thereby improving the data compression efficiency.

The above-mentioned encoder 10 and decoder 30 can each be configured as a computer device.

Figure 17 is a configuration diagram of a computer device according to one embodiment. Note that in this embodiment, the encoder 10 and the decoder 30 are configured as separate computer devices, but these computer devices can have similar configurations. Therefore, for the sake of convenience, in the following explanation, the computer device that constitutes the encoder 10 and the decoder 30 will be explained using the computer device shown in Figure 17.

The computer device 100 includes, for example, a Central Processing Unit (CPU) 101, a main memory 102, a Graphics Processing Unit (GPU) 103, a reader/writer 104, a communication interface (communication I/F) 105, an auxiliary storage device 106, an input/output interface (input/output I/F) 107, an output device 108, and an input device 109. The CPU 101, the main memory 102, the GPU 103, the reader/writer 104, the communication I/F 105, the auxiliary storage device 106, the input/output I/F 107, and the output device 108 are connected via a bus 110. The encoder 10 and the decoder 30 are each configured by appropriately selecting some or all of the components described in the computer device 100.

In the computer device 100 constituting the encoder 10, the CPU 101 executes a processing program stored in the auxiliary storage device 106 to constitute, for example, a target data input unit 11, a prediction difference calculation unit 12, an encoding unit 13, and a compressed data output unit 14.

In the computer device 100 constituting the decoder 30, the CPU 101 executes a processing program stored in the auxiliary storage device 106 to constitute, for example, a compressed data input unit 31, an encoding/decoding unit 32, a target data calculation unit 33, and a target data processing unit 34.

The main memory 102 is, for example, a RAM, a ROM, etc., and stores programs (processing programs, etc.) executed by the CPU 101 and various information. The auxiliary storage device 106 is, for example, a non-transitory storage device (non-volatile storage device) such as a hard disk drive (HDD) or a solid state drive (SSD), and stores programs executed by the CPU 101 and various information.

The GPU 103 is, for example, a processor that is suitable for executing a specific process, for example, a process that is performed in parallel. In this embodiment, the GPU 103 executes a predetermined process according to instructions from the CPU 101.

The reader/writer 104 is detachable from the recording medium 111, and reads data from the recording medium 111 and writes data to the recording medium 111. The recording medium 111 may be, for example, a non-temporary recording medium (non-volatile recording medium) such as an SD memory card, a floppy disk (FD: registered trademark), a CD, a DVD, a BD (registered trademark), or a flash memory. In this embodiment, a processing program may be stored in the recording medium 111, and the reader/writer 104 may read and use the program. In the computer device 100 constituting the encoder 10, audio data to be processed may be stored in the recording medium 111, and the reader/writer 104 may read and use the program. In the computer device 100 constituting the encoder 10, the reader/writer 104 may store compressed data in the recording medium 111. In the computer device 100 constituting the decoder 30, the reader/writer 104 may read and use the compressed data from the recording medium 111.

The communication I/F 105 is connected to the network 50 and transmits and receives data to and from other devices connected to the network 50.

The input/output I/F 107 is connected to an input device 109 such as a mouse or a keyboard. In the computer device 100 constituting the encoder 10, the input/output I/F 107 accepts operational input by a user of the encoder 10 using the input device 109. In the computer device 100 constituting the decoder 30, the input/output I/F 107 accepts operational input by a user of the decoder 30 using the input device 109.

The output device 108 is, for example, a display device such as an LCD display or a speaker device, and outputs various types of information and audio. The output device 108 is used, for example, in the decoder 30, for audio output by the target data processing unit 34.

The present invention is not limited to the above-described embodiment and modifications, and may be modified as appropriate without departing from the spirit of the present invention.

For example, in the above embodiment, the encoder 10 creates a file for the entire target data and transmits the file to the decoder 30. The present invention is not limited to this, and the encoder 10 may, for example, transmit compressed data for each block sequentially.

In addition, in the above embodiment, the original data is encoded without distortion, but the present invention is not limited to this, and the original data may be encoded after distortion processing such as quantization.

In addition, in the above embodiment, the target of encoding is audio data, but the present invention is not limited to this, and the target of encoding may be data other than audio, for example, image data.

In addition, in the above embodiment, an example was shown in which the computer device 100 includes either the encoder 10 or the decoder 30. The present invention is not limited to this, and the computer device 100 may include both the encoder 10 and the decoder 30.

1... Processing system, 10... Encoder, 11... Target data input unit, 12... Prediction difference calculation unit, 13... Encoding unit, 14... Compressed data output unit, 30... Decoder, 31... Compressed data input unit, 32... Encoding/decoding unit, 33... Target data calculation unit, 34... Target data processing unit, 50... Network, 100... Computer device, 101... CPU, 102... Main memory, 108... Output device, 111... Recording medium

Claims (9)

1. An encoder for encoding encoding target data including a plurality of integer values, comprising:
an identification unit that identifies block data in which a plurality of integer values are arranged from the encoding target data;
An encoder that encodes the block data into a combined code that combines a plurality of alpha codes and a CBT code. The encoder according to claim 1 , wherein the encoding unit encodes a plurality of types of block data into a combined code in which the plurality of alpha codes have the same value and the CBT code has a different value. The encoder according to claim 2 , wherein the encoding unit determines the plurality of alpha code values to be assigned to the block data based on an occurrence probability of the sequence of the plurality of integer values of the block data. The encoder according to claim 3 , wherein the encoding section performs encoding such that the plurality of alpha codes assigned to the block data having a high occurrence probability tend to be short. The encoder according to claim 3 , wherein the encoding unit performs encoding so that the CBT code assigned to the block data having a high occurrence probability is short. The encoder of claim 1 , further comprising a transmitter for transmitting the combined code to an encoder. A decoder for decoding encoded data, comprising:
The encoded data includes a combined code obtained by encoding block data in which a plurality of integer values are arranged, the combined code being a combination of a plurality of alpha codes and a CBT code,
A reception unit that receives the encoded data;
a decoding unit configured to decode a combined code included in the encoded data into the plurality of integer values. An encoding method for encoding target data including a plurality of integer values, comprising:
Identifying a block of data in which a plurality of integer values are arranged from the encoding target data;
An encoding method for encoding the block data into a combined code that combines a plurality of alpha codes and a CBT code. A decoding method for decoding encoded data, comprising:
The encoded data includes a combined code obtained by encoding block data in which a plurality of integer values are arranged, the combined code being a combination of a plurality of alpha codes and a CBT code,
Accepts the encoded data,
A decoding method for decoding a combined code included in the encoded data into the plurality of integer values.