KR101168158B1 - Address generator for searching an algebraic code book - Google Patents

Abstract

The present invention relates to an address generator for algebraic codebook retrieval, the apparatus comprising: a multiplier for multiplying a magnitude and a horizontal value of a correlation matrix; a first adder and a multiplier and a first adder for adding a vertical value and an offset address of the correlation matrix; And a second adder for generating an address for algebraic codebook search by summing the calculation results of the adder, thereby reducing the amount of computation required when calculating an address for algebraic codebook search.

Algebra Codebook Search, Address Generator, Address Calculation

Description

Address generator for searching an algebraic code book

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to algebraic codebook retrieval technology in an ACELP type voice codec, and more particularly, to an address generator for algebraic codebook retrieval that can reduce the amount of address computation for algebraic codebook retrieval.

The present invention is derived from the research conducted as part of the IT source technology development project of the Ministry of Knowledge Economy and the Ministry of Information and Communication Research and Development. [Task management number: 2006-S-048-03] ].

In digital mobile communication system, the bandwidth of the transmission channel is efficiently used and various voice coding algorithms are used for high quality call in the wireless channel environment.

In general, the Code Excited Linear Prediction (CELP) algorithm, adopted by many standards among voice codec algorithms, shows very good performance at low data rates of 4 to 8 kbps.

These CELP algorithms have been further improved to shorten the search time of fixed codebooks, and have been developed into ACELP (Algebraic CELP), which requires no memory for codebooks, and is widely adopted and used in most of the recent world standards.

Since the algebraic codebook algorithm adopted by the ACELP type voice codec does not use the codebook to model the excitation signal, it does not need the storage space for the codebook and the codebook search method uses efficient methods, so it can be searched with a small amount of computation. have.

However, even in the algebraic codebook algorithm, a relatively large amount of computation is required in the process of searching for the position and magnitude of the pulse of the excitation signal that has the least error with the target signal.

In order to reduce the amount of computation in the search process, a focused search method and a depth first tree search method have been proposed and used.

The intensive search method used in the G.729 voice codec is to limit the search range using thresholds, and the depth-first branch search method used in G.729A uses local maximum values to reduce the computation more effectively than the intensive search method. This method searches only the paths that satisfy the. Most other ACELP type voice codecs adopt intensive search method and depth-first search method to reduce search computation.

The real-time implementation of voice codecs is generally using a commercial DSP (Digital Signal Processor). That is, after selecting a commercial DSP suitable for the algorithm of the voice codec to be implemented, the compiler and assembler are used to obtain the optimal implementation result by maximizing the characteristics of the selected DSP.

In addition, if necessary, by designing a DSP that can further optimize the algorithm of the voice codec and implementing the voice codec based on this, the most optimal performance is obtained.

However, such an implementation method requires a long time to develop a DSP, and the developed DSP can be optimally implemented for a specific voice codec algorithm, but may not be optimal for the implementation of a voice codec using another algorithm. have.

On the other hand, in the algebraic codebook search of the ACELP type voice codec, correlation matrix values are precomputed before the search and the values are used in the search process.

However, while these correlation matrix values are two-dimensional array values, what is actually stored in the memory has a feature that is implemented as a one-dimensional array.

In order to use the correlation matrix values stored in the one-dimensional array in the actual algebraic codebook retrieval process, proper address calculation must be involved. When implemented in a general commercial DSP assembly language, a calculation amount of about 5 cycles is required.

Since this calculation must be repeated in the algebraic codebook retrieval process, this is a major factor to increase the calculation amount of the algebraic codebook retrieval process.

Accordingly, in the present invention, an address that can easily generate an address value of a memory storing the correlation matrix value in order to reduce the amount of computation for accessing the correlation matrix values that occupy a very large portion in the algebraic codebook search process. We want to provide a generator.

According to a first aspect of the present invention, as a means for solving the above problems, a multiplier for multiplying the magnitude and the horizontal value of the correlation matrix, the first adder and the multiplier and the sum of the vertical value and the offset address of the correlation matrix An address generator for algebraic codebook retrieval comprising a second adder that adds the calculation results of the first adder to generate an address for algebraic codebook retrieval.

The address generator may further include a register that stores a calculation result of the second adder.

The address generated by the second adder may be an address to be accessed first of the memory of the correlation matrix.

According to the second aspect of the present invention, as a means for solving the above problems, a variable of a two-dimensional array that stores correlation matrix values during algebraic codebook retrieval using an address generator according to the first aspect of the present invention. An apparatus for encoding an ACELP type speech codec, which generates an address for accessing a one-dimensional memory from a value.

As described above, the address generator for algebraic codebook retrieval simply generates an address value of a memory storing a correlation matrix value, thereby accessing correlation matrix values that occupy a very large part in the algebraic codebook retrieval process. This reduces the amount of address computation. Accordingly, in the present invention, the algebraic codebook retrieval efficiency can be increased and the calculation speed can be improved.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. However, in describing in detail the operating principle of the preferred embodiment of the present invention, if it is determined that the detailed description of the related known function or configuration may unnecessarily obscure the subject matter of the present invention, the detailed description thereof will be omitted.

In order to clearly illustrate the present invention, parts not related to the description are omitted, and like parts are denoted by similar reference numerals throughout the specification.

In addition, when a part is said to include a certain component, this means that it may further include other components, without excluding other components unless otherwise stated.

Prior to generating an address generator according to an embodiment of the present invention, a general ACELP-type speech codec encoding apparatus, a C code for algebraic codebook search, a correlation matrix for algebraic codebook search, and When the correlation matrix array is implemented in real time using a DSP, a process of storing the one-dimensional memory will be described first.

1 is a diagram showing the configuration of an encoding apparatus for a general ACELP type voice codec.

Referring to FIG. 1, an apparatus for encoding an ACELP type speech codec includes a linear analyzer 10, an LSP (Line Spectral Pair) converter 11, an LSP quantizer 12, an open loop pitch search unit 13, and a closed loop. It includes a loop pitch search unit 14, an impulse response calculation unit 15, a first target signal calculator 16, a second target signal calculator 17, and an algebraic codebook search 18. do.

The linear analyzer 10 calculates 10th order linear predictive coding (LPC) coefficients using 160 samples (20 msec) of a speech signal sampled at 8 kHz as one frame. Preferably, the linear analysis unit 10 performs two linear analyzes per frame in the case of a high bit rate, and in most cases, performs only one linear analysis per frame.

The LSP converter 11 converts the LPC coefficients into LSP coefficients having good quantization distortion and transmission error and having good interpolation characteristics.

The LSP quantization unit 12 performs vector quantization of the LSP coefficients through various algorithms such as split matrix quantization (SMQ) and split vector quantization (SVQ).

The open loop pitch search unit 13 first determines an integer delay value through an open loop pitch search operation in order to reduce the amount of calculation for the pitch search.

The closed loop pitch searching unit 14 performs the closed loop searching operation only on the peripheral values based on the integer delay value determined by the open loop pitch searching unit 13. In this case, the open loop pitch search is performed on the weighted speech signal, and is performed once per frame in the case of a low data rate, and twice per frame in the case of a high data rate.

After the open loop search is completed, the impulse response calculator 15 and the first target signal calculator 16 output the impulse response h (n) and the first target signal x (n) for the closed loop search. Calculate At this time, the first target signal x (n) is calculated by removing the zero input response signal of the weighted synthesis filter from the weighted input speech signal. In the closed loop search, the delay value of the integer value that minimizes the mean square error between the target signal and the synthesized speech signal is determined with respect to the surrounding value of the previously obtained open loop delay value.

The second target signal calculator 17 calculates the second target signal x ₂ (n) in order to perform a logarithmic codebook search. The secondary target signal x ₂ (n) is obtained by removing the pitch component from the primary target signal x (n).

The algebraic codebook search unit 18 determines the position and the sign of the pulse which minimizes the mean square error between the second target signal x ₂ (n) and the synthesized speech signal. That is, it searches for algebra codebooks.

Algebra codebooks occupy a large portion of bit allocation in ACELP-type speech codecs, and the number of pulses per subframe can be used from several tens to one according to various bit rates.

For example, if a subframe is divided into five tracks, two pulses are defined for each track, and the position and sign information are transmitted, the algebraic codebook is configured using a total of ten pulses. If the subframe is divided into four tracks and modeled using two pulses for each track, the algebraic codebook is composed of eight pulses in total.

The algebraic codebook search process in the ACELP speech codec is a process of finding a pulse train of an excitation signal that minimizes the mean square error between the input voice and the synthesized voice, as shown in Equation 1 below.

Where x is the first target signal x (n) from which the predictive gain of the adaptive codebook has been removed, g is the codebook gain, H = h ^t h is the lower triangular Toeplitz convolution matrix, C _k is an algebraic code vector whose index is k.

Minimizing Equation 1 has the same meaning as maximizing Equation 2 below.

In this case, d is a signal indicating the correlation between the first target signal x (n) and the impulse response h (n), and is referred to as a target signal that is inversely filtered, and Ф = H ^t H is h (n). Is the correlation matrix.

Since the algebraic code vector C _k is composed of a small number of nonzero pulses, the molecular term in Equation 2 is expressed as in Equation 3 below, and the denominator term is expressed in Equation 4 below.

At this time, m _i is the position of the i-th pulse, s _i is the sign of the pulse, N _p is the number of pulses.

The d (m _i ) signal and the correlation matrix Ф (m _i , m _j ) in Equation 3 are preferably calculated before the search process in order to reduce the amount of computation in the search process.

Among the algebraic codebook retrieval methods, since the entire retrieval method has a large number of combinations of pulses, an intensive retrieval method or a depth-first branch retrieval method is used for more efficient retrieval.

In order to simplify the search process, the intensive search method uses a pre-calculated threshold value before searching for the last loop to enter the loop and continue the search only when the threshold value is exceeded.

The depth-first search method is an improvement on the intensive search method. It selects the local maximum value of each track as the initial pulse and selects the local optimal value, and searches only the most probable tree. .

In addition, the algebraic codebook algorithm divides a subframe into predetermined tracks and allocates a predetermined number of pulses to each track in order to efficiently model the excitation signal of the subframe. Also, the magnitude of each pulse is fixed to '± 1' in advance in order to reduce the calculation amount in the searching process.

FIG. 2 is a diagram illustrating an embodiment of a C code for algebraic codebook search of a TETRA voice codec, which is one of ACELP type voice codecs.

In Figure 2, the C codes of 21, 22, 24, and 26 represent nested loops, and the C codes of 23 and 25 allow to examine the threshold for determining whether to join into the nested loop. .

Referring to the C code, it can be seen that in the search of the algebraic codebook, rr [] [], which is an autocorrelation matrix of h (n) of an impulse response, is repeatedly used.

에서 분모항의 에너지(E)를 계산할 때 수학식5에서와 같은 계산이 이루어지고, 이를 위해서는 상관관계 매트릭스 Ф(m_i, m_j)가 반복 사용된다. Of equation (2)

When calculating the energy (E) of the denominator in, the same calculation as in Equation 5 is performed, and the correlation matrix Ф (m _i , m _j ) is used repeatedly for this purpose.

E = a ² Ф (m ₀ , m ₀ ) + Ф (m ₁ , m ₁ ) -2aФ (m ₀ , m ₁ ) + Ф (m ₂ , m ₂ ) + 2aФ (m ₀ , m ₂ )-2aФ (m ₁ , m ₂ ) + Ф (m ₃ , m ₃ ) -2aФ (m ₀ , m ₃ ) + 2Ф (m ₁ , m ₃ ) -2Ф (m ₂ , m ₃ )

At this time, the values of Ф (m _i , m _j ) are calculated before retrieval and stored in memory in advance.

Since Ф (m _i , m _j ) is a matrix type, it is preferable to store it in a memory of a two-dimensional array structure when implemented in C code, but as described above, in a real-time implementation in a real-time DSP, it is stored in a one-dimensional memory. There is.

As a result, many cycles are required to generate an address for accessing Ф (m _i , m _j ) stored in the one-dimensional memory. That is, a problem arises in that the amount of address calculation increases.

For example, in the case of the Tetra codec, the correlation matrix is configured as shown in FIG. 3.

In the case of the Tetra codec, the length of the subframe is 60, but since only correlation values for even numbers are needed, the length of the impulse response h (n) is 30. The correlation matrix for the impulse response of h (0) to h (29) may be obtained. However, the dimension of the correlation matrix in the log structure of the algebraic codebook is 32, so that [30], [ 31] elements are zero.

FIG. 4 is a diagram illustrating a process of storing the correlation matrix array 41 of FIG. 3 in the one-dimensional memory 42 when the correlation matrix array 41 is implemented in real time using a DSP.

The correlation matrix of FIG. 4 has diagonal elements of rr [0] [0] to rr [29] [29], and the lower and higher triangle elements are the same, that is, rr [i] [ j] = rr [j] [i]. The last element of this matrix in one-dimensional memory, that is, the address of rr [29] [29], becomes '32 × 29 + 29 = 957 '.

As described above, in the execution of the nested loop form, which takes up the largest amount of computation in the algebraic codebook search, the variable values of the two-dimensional matrix structure are continuously used in the calculation for the search of the algebraic codebook.

Therefore, by designing an address generator that can be easily accessed when a variable having a two-dimensional matrix configuration is implemented in a one-dimensional memory in real time, it is possible to drastically reduce the computational complexity of algebraic codebooks.

However, when accessing the variable value of the two-dimensional matrix structure in C code as shown in FIG. 2, in the real-time implementation, the matrix structure 41 of the two-dimensional array is implemented as the memory 42 of the one-dimensional structure as shown in FIG. 4. As a result, the address calculation process becomes complicated, and a larger amount of calculation is required.

If the address calculation process is implemented in the assembly language of TI DSP 54X series, which is widely used among commercial DSPs, it can be implemented as follows.

C code Assembly code

rr [ii0] [ii2] STM # 32, T

MPY @ ii0, A

ADD @ ii2, A

ADD #rr, A

STLM A, AR3

Here, 32 is the dimension of the matrix, and the #rr value is the start address of the matrix, that is, the offset address.

That is, in order to access a two-dimensional variable value of rr [ii0] [ii2] in the C code of FIG. 2, when implemented in assembly language, five instructions are required, and as a result, about five cycles of calculation amount are required.

Since this calculation must be repeated in the algebraic codebook retrieval process, this is a major factor in increasing the computational volume of the algebraic codebook retrieval process.

Therefore, the present invention proposes an address generator that can configure these five instructions into one instruction, and dramatically reduces the amount of computation required for the address calculation process.

That is, the present invention proposes an address generator for generating an address for accessing a one-dimensional memory from a variable value of a two-dimensional array that stores a correlation matrix value in algebraic codebook retrieval.

5 is a diagram illustrating a configuration of an address generator according to an embodiment of the present invention.

Referring to FIG. 5, the address generator of the present invention includes a multiplier 21 for multiplying a dimension of a correlation matrix and a row, and a first adder for adding a column and an offset address. (22), a second adder 23 which sums up the calculation results of the multiplier 21 and the first adder 23, and a register 24 which stores the calculation result of the second adder 23.

Accordingly, the address generator of the present invention replaces the five instructions described above with one instruction as follows, thereby generating an address for accessing the one-dimensional memory from the addresses of the two-dimensional array.

STM & (raw, column), AR3

At this time, raw is the horizontal value of the address of the two-dimensional array, column is the vertical value of the address of the two-dimensional array, AR3 means the register 24 for generating the operation result value of the address generator.

For reference, in the algebraic codebook retrieval process, the operation according to the address generator of FIG. 5 generates an address for obtaining a two-dimensional correlation value from the one-dimensional memory, but from the DSP hardware point of view, the operation according to the address generator of FIG. Can be thought of as a command that generates a specific value and stores it in a register.

Therefore, the address generator of the present invention can be thought of as hardware that actually performs a specific instruction that is distinct from the address generation block of the DSP hardware.

The address value generated by the address generator of the present invention is the first address to be accessed in the correlation matrix memory, and actually addressing is performed while the address register values increase by a step value in the overlapping loop.

In the present invention, the bit calculation amount of the multiplier 21 is set to 8 × 8 (bit × bit), but this can be actively changed according to the characteristics of the ACELP speech codec. For example, when the address generator of the present invention is applied to the Tetra codec, the multiplier 21 may be designed as 5x5. The first and second adders 22 and 23 may be 16 bits long.

The dimension and offset address of the matrix are set in advance outside the nested loop, and in the nested loop, only the raw and column values are supplied as operands.

Therefore, the address generator of the present invention replaces five instructions according to the prior art with one instruction and replaces an address for accessing the one-dimensional memory from the raw and vertical values of the two-dimensional array. Create

Hereinafter, when using the address generator of the present invention, the effect of reducing the amount of address calculation for matrix memory access when searching the ACELP algebra codebook will be described.

Since this prediction is greatly affected by the DSP hardware, the present invention will be described in terms of address computation reduction based on the TI 320C54X.

First, in the case of the Tetra codec, the number of searches in the nested loop of the C code as shown in FIG. 2 is as follows.

1) If the first threshold value THR1 is not exceeded: 30 × 8 = 240

2) When the first threshold value THR1 is exceeded and the second threshold value THR2 is not exceeded: 30 × 8 × 8 = 1,920

3) When the first threshold value THR1 and the second threshold value THR2 are all exceeded: 30 × 8 × 8 × 8 = 15,360

However, if any one of the thresholds is exceeded, the logic that limits the maximum number of searches is operated, so the actual number of searches is reduced more than the number of searches above.

The logic for limiting the maximum number of searches is to set the counter to 350 before entering the loop, and then decrease 4 if the first threshold value THR1 is passed and decrease the value to 4 if the second threshold value THR2 is passed. In other words, if the innermost loop is performed, it is set to decrease 3.

Therefore, applying this maximum number of search limit logic, the two innermost loops are actually about 13 times. Therefore, the maximum number of searches is reduced as follows.

1) If the first threshold value THR1 is not exceeded: 30 × 8 = 240

2) When the first threshold value THR1 is exceeded and the second threshold value THR2 is not exceeded: 153 + 87 × 8 = 849

3) When the first threshold value THR1 and the second threshold value THR2 are all exceeded: 227 + 13 × 64 = 1,059

Referring to the number of searches and the C code for the search loop, it is possible to calculate how much calculation is required for address calculation for the matrix memory as follows. You can also predict if you can.

Looking at the C code for the search loop of Figure 2, rr [i0] [i0] in the first loop, rr [i1] [i1], rr [i0] [i1] in the second loop, and rr [i2 in the third loop. ] [i2], rr [i0] [i2], rr [i1] [i2], in the fourth loop rr [i3] [i3], rr [i1] [i3], rr [i0] [i3], rr Address calculation for the memory of [i2] [i3] is necessary.

In the assembly code described above, assuming that the matrix dimension is set to '32', the number of cycles required for each address calculation is '4' cycles. The amount of calculation is calculated as follows.

1) {30 + 30 × 2 + (8 × 3 + 8 × 8 × 4) × 13} × 4 = 149,200

2) 14,920 × 4 subframes × 33 frames / sec = 1.97 MIPS

However, since the address generator of the present invention is reduced to 1/4, the calculation amount for address retrieval is finally reduced to about 0.5 MIPS.

In the case of the G.729 codec, the number of searches in the loop of the C code as shown in FIG. 2 is calculated as follows.

1) If the threshold (THR) is never exceeded: 8 × 8 × 8 = 512

2) When the threshold (THR) is exceeded: 8 × 8 × 8 × 16 = 8,192

However, if the threshold is exceeded, the logic that limits the maximum number of searches is operated, so the actual number of searches is reduced more than the number of searches above.

The logic for limiting the maximum number of searches is determined by counting the number of times the last loop is executed by passing the threshold. Therefore, when the maximum number of search limit logic is applied, the innermost loop is actually performed 105 times in the first subframe and 180 times in the second subframe.

1) If the threshold (THR) is never exceeded: 8 × 8 × 8 = 512

2) When the threshold (THR) is exceeded:

3) Subframe 0: (512-105) + 105 × 16 = 2,087,

4) Subframe 1: (512-180) + 180 × 16 = 3212

5) Accessing a two-dimensional matrix type memory in a loop is almost similar to the Tetra codec. Therefore, the number of cycles required for each address calculation is as follows.

1) ((8 + 8 × 2 + 8 × 8 × 3) × (512-105) / 512 + 105 × 16 × 4} × 4 + {(8 + 8 × 2 + 8 × 8 × 3) × ( 512-180) / 512 + 180 × 16 × 4} × 4 = 27,568 + 46,640 = 74,208,

2) 74,208 × 100 frame / sec = 7.4 MIPS

Here again, when the matrix address generator of the present invention is used, the calculation amount is reduced to 1/4, and thus the calculation amount is reduced to about 1.85 MIPS.

The present invention described above is not limited to the above-described embodiments and the accompanying drawings, and it is common in the art that various substitutions, modifications, and changes can be made without departing from the technical spirit of the present invention. It will be apparent to those skilled in the art.

1 is a diagram showing the configuration of an encoding apparatus for a general ACELP type voice codec.

FIG. 2 is a diagram showing an embodiment of a C code of algebraic codebook search of a TETRA voice codec, which is one of ACELP type voice codecs. FIG.

3 is a diagram illustrating an example of a correlation matrix for algebraic codebook search.

4 is a diagram illustrating a process of storing the correlation matrix array of FIG. 3 in a one-dimensional memory when the correlation matrix array of FIG. 3 is implemented in real time using a DSP.

5 is a diagram illustrating a configuration of an address generator according to an embodiment of the present invention.

Claims (4)

A multiplier that multiplies the magnitude of the correlation matrix by the horizontal value; A first adder for adding up a vertical value and an offset address of the correlation matrix; And And a second adder for generating an address for algebraic codebook search by summing calculation results of the multiplier and the first adder. The method of claim 1, And a register for storing a calculation result of the second adder. The method of claim 1, And the address generated by the second adder is an address to be accessed first of the memory of the correlation matrix. Using the address generator according to any one of claims 1 to 3, an address for accessing a one-dimensional memory is generated from a variable value of a two-dimensional array that stores correlation matrix values during algebraic codebook retrieval. An apparatus for encoding an ACELP type speech codec.

Images