TWI863310B - Speedy decoder of qc ldpc codes - Google Patents

Abstract

The present invention refers to a fast decoder for quasi-cyclic low-density parity check codes, including an input register, a data selection multiplexer, a bit flip and symptom value update module, a symptom value register, a data register, a flip state update module, and a decoding termination module. The bit flip and symptom value update module includes a flip threshold value selection logic circuit, a partial flip function value correspondence and flip function value operation logic circuit, and a flip vector judgment logic circuit.

Description

Fast decoder for quasi-cyclic low-density parity-check codes

The present invention relates to a decoder, in particular a decoder for quasi-cyclic low-density parity-check codes (QC LDPC Codes).

Traditional bit flipping (BF) decoders have several main modules: data register, symptom value calculation module, shifter, flip function value calculation module, flip threshold value determination module, bit flip determination module. The above modules must be run in each loop.

How to strike a balance between the decoder's speed, area, power consumption and decoding effect, or to increase the decoder's speed while slightly increasing the area and improve the decoding capability without increasing power consumption, is an issue that the industry needs to solve urgently.

In view of the above problems of the prior art, the purpose of the present invention is to provide an accurate, fast and low-power quasi-cyclic low-density parity check code flip decoder.

To achieve the above purpose, the decoder includes an input register, a symptom value register, a data register, a data selection multiplexer, a bit flip and symptom value update module, a flip state update module, and a decoding termination module. The bit flip and symptom value update module includes a flip threshold selection logic circuit, a partial flip function value correspondence and a flip function value operation logic circuit, and a flip vector judgment logic circuit.

10: Input register

20: Data selection multiplexer

30: Bit flip and symptom value update module

31: Flip threshold to select logic circuit

的翻轉函數值計算與對應邏輯電路 32: Symptom value

Calculation of flip function value and corresponding logic circuit

的翻轉函數值計算與對應邏輯電路 33: Symptom value

Calculation of flip function value and corresponding logic circuit

34: Final flip function operation and maximum flip function value search logic circuit

35: Bit flip logic circuit

36: First Mutex OR Logic Circuit

37: Second mutex or logic circuit

39: The first barrel shifter

38: Second barrel shifter

40: Symptom value register

50: Data register

60: Flip status update module

70: Decoding termination module

[Figure 1] is a block diagram of a circuit of a fast decoder of a quasi-cyclic low-density parity-check code according to an embodiment of the present invention.

[Figure 2] is a block diagram of the circuit of the flip bit and symptom value update module in Figure 1.

[Figure 3] is a schematic diagram of vector F.

[Figure 4] shows the vector F represented by the address and w bits.

[Figure 5] shows the representation of only five units in vector F.

(N,K) Quasi-Cyclic Low Density Parity Check codes (QC LDPC codes) are a type of linear code, where N is the length of the codeword and K is the length of the transmitted information. We define an LDPC code by a parity check matrix H, where the dimension of H is M×N.

而得症狀值(syndrome)

R^T，R^T是R的轉置矩陣(transpose matrix)，

且它的維度是M×1。 The received codeword R has length N, R = [r ₀ ,r ₁ ,r ₂ ,…,r _N-1 ]. Flipped vector

The symptom value (syndrome)

^RT , ^RT is the transpose matrix of R,

And its dimension is M×1.

For each bit j, the common flip function is as follows:

；或

;or

。

.

In the above two equations, M(n) is the position of 1 in the nth row of H, and W _k,n is the weight. In one embodiment of the present invention, the weight W _k,n = 1, and the inversion function can be simplified as:

In this embodiment, the column weight of the quasi-cyclic LDPC code is 3 or 4, that is, col_wt(n)=3 or 4, n=0,1,…,N-1.

In order to increase the decoding speed and decoding capability, we add the symptom value of the initially received codeword and the influence of the previous flip vector to the calculation of the flip function. Therefore, it is necessary to store the symptom value of the initially received codeword and the array flip vector. In this way, the decoding speed and decoding capability are increased.

輸入應用公式(1)，得到

。把

數值依大小分成數個不相交的區間，使這些區間分別對應輸入給定的數值表。在本實施例，

{-4,-3,-2,-1,0,1,2,3,4}。我們給定對應輸入數值表為[-4,-4,-2,-1,0,1,2,3,3]。收到的

經公式(1)運算而得到

。然後，依對應數值表，輸出對應數值

。 The symptom value of the first received codeword

Enter the application formula (1) and get

.Bundle

The values are divided into several non-overlapping intervals according to their size, so that these intervals correspond to the given input value table. In this embodiment,

{-4,-3,-2,-1,0,1,2,3,4}. We give the corresponding input value table as [-4,-4,-2,-1,0,1,2,3,3].

The formula (1) is used to calculate

Then, according to the corresponding value table, output the corresponding value

.

Initialize the flip vector to all zeros. In the first iteration, use formula (1) to calculate the flip function value.

與前次的翻轉向量

，即 In the second recursion, if the sum of the symptom value bits is less than the given value D, the flip function value E ' ^(t) is combined with the value generated by the initial symptom value

Flip vector from last time

,Right now

的影響，即 If the sum of the symptom value bits is greater than or equal to the given value D, the flip function value E ' ^(t) only considers the previous flip vector

The impact of

In this embodiment, D=20. 20 is a value obtained through testing, and D may be other appropriate values.

、

、

、

與些許運算邏輯。 In this embodiment, four sets of flip vectors are stored

,

,

,

and a little bit of computational logic.

。

中任一個位元為1，即有位元翻轉，更新三組翻轉向量

、

、

。令

，

，

。 After determining the flip vector for each block, temporarily store the flip vector

.

If any bit in the bit is 1, there is a bit flip, and the three sets of flip vectors are updated.

,

,

.make

,

,

.

是否與

完全相同。 compare

Whether

Exactly the same.

，則全等訊號(all_eq)=1，否則全等訊號=0-(4) like

, then the congruence signal (all_eq) = 1, otherwise the congruence signal = 0-(4)

與

進行及(and)運算，並對

與

進行及(and)運算。另外，計算

的位元總和。 right

and

Perform and operation and

and

Perform and operation. In addition, calculate

The sum of the bits.

Oscillation signal 1

Oscillation signal 2

The oscillation signal is oscillation signal 1 or oscillation signal 2------------------------------(7)

The variable d and the array of previous flip vectors can be adjusted according to the channel state and the structure of the LDPC code. In this embodiment, d=5, and three sets of previous flip vectors are used.

更新症狀值。 Use congruent signals and oscillating signals with

Updates symptom values.

The previous flip signal (bit_pre_flip) records whether any bit was flipped in the previous pass. In this embodiment, bit_pre_flip=1 by default. After each complete flip vector is determined, if there is a flipped bit, bit_pre_flip=0, otherwise bit_pre_flip=1.

E_th，則翻轉第n位元。 Regarding the flip threshold (E_th), if _En

E_th, then flip the nth bit.

The E_th value can be given dynamically or according to matrix characteristics.

Based on the optimization considerations of hardware implementation, in this embodiment, when the column weight distribution of the parity check matrix is four or three, the E_th value is given as follows:

If the iteration number = 1, then E_th = 4;

If the iteration count>1, and the previous flip signal = 0, there are three situations to judge:

If the congruent signal is 1, then E_th=E_th-2. If the congruent signal is 0, then the oscillation signal is 1, and E_th=2. Otherwise, E_th=3.

If the iteration number>1, and the previous flip signal bit_pre_flip=1, then E_th=max_E _n .

，如上述，若E_n

E_th，則翻轉第n個位元，即f_n=1。 About flipping vectors

As mentioned above, if E _n

E_th, then flip the nth bit, that is, f _n =1.

To perform the above tasks, the present invention provides a fast decoder for quasi-cyclic low-density parity check codes. Referring to FIG. 1 , according to a preferred embodiment of the present invention, the decoder includes an input register 10, a data selection multiplexer 20, a bit flip and symptom value update module 30, a symptom value register 40, a data register 50, a flip state update module 60, and a decoding termination module 70. The input register 10 is connected to the data selection multiplexer 20. The data selection multiplexer 20 is also connected to the bit flip and symptom value update module 30. The bit flip and symptom value update module 30 is also connected to the symptom value register 40, the data register 50, and the flip state update module 60. The decoding termination module 70 is connected to the symptom value register 40.

During operation, the input register 10 receives a codeword, stores the received codeword, and transmits the received codeword to the data selection multiplexer 20.

If the recursive number = 1, the data selection multiplexer 20 transmits the data of the input register 10 to the bit flip and symptom value update module 30, otherwise, the data of the data register 50 is transmitted to the bit flip and symptom value update module 30.

The bit flip and symptom value update module 30 generates a flip vector, flipped data, and updated symptom value after comparing the selected flip threshold with the calculated flip function. The bit flip and symptom value update module 30 receives the first generated symptom value and the updated symptom value from the symptom value register 40. Then, the bit flip and symptom value update module 30 transmits the first generated symptom value, the updated symptom value, and the flipped data to the data register 50. In addition, the bit flip and symptom value update module 30 transmits the previous flip signal and the flip vector to the flip state update module 60.

In addition, the data register 50 transmits the flipped data to the data selection multiplexer 20, thereby allowing the data selection multiplexer 20 to select.

，並把這些訊號傳至位元翻轉及症狀值更新模組30。 The flip state update module 60 executes formulas (4), (5), (6), and (7) to update the congruent signal, the oscillation signal, and

, and transmit these signals to the bit flip and symptom value update module 30.

The decoding termination module 70 receives the bit sum of the symptom value from the symptom value register 40 and generates a decoding status output signal accordingly. The decoding status output signal represents continued decoding, successful decoding, almost successful decoding, and failed decoding. The output signal is provided to the external decoding process state machine module to control the decoding process.

的翻轉函數值計算與對應邏輯電路32、症狀值

的翻轉函數值計算與對應邏輯電路33、最終翻轉函數運算與最大翻轉函數值搜尋邏輯電路34、翻轉位元邏輯電路35、第一互斥或邏輯電路36、第二互斥或邏輯電路37、第一桶式移位器39及第二桶式移位器38。 To perform the above tasks, a bit flip and symptom value update module 30 is provided. The bit flip and symptom value update module 30 includes a flip threshold value selection logic circuit 31, a symptom value

Calculation of flip function value and corresponding logic circuit 32, symptom value

The flip function value calculation and corresponding logic circuit 33, the final flip function operation and maximum flip function value search logic circuit 34, the flip bit logic circuit 35, the first exclusive OR logic circuit 36, the second exclusive OR logic circuit 37, the first barrel shifter 39 and the second barrel shifter 38.

The flip threshold selection logic circuit 31 is connected to the data selection multiplexer 20 and the final flip function operation logic circuit 34 at the input end, and is connected to the flip bit logic circuit 35 at the output end.

的翻轉函數值計算與對應邏輯電路32於輸入端連接第一桶式移位器39，並於輸出端連接最終翻轉函數運算與最大翻轉函數值搜尋邏輯電路34的輸入端。 Symptom value

The flip function value calculation and corresponding logic circuit 32 is connected to the first barrel shifter 39 at the input end, and is connected to the input end of the final flip function operation and maximum flip function value search logic circuit 34 at the output end.

的翻轉函數值計算與對應邏輯電路33於輸入端連接第一桶式移位器39，並於輸出端連接最終翻轉函數運算與最大翻轉函數值搜尋邏輯電路34的輸入端。 Similarly, symptom values

The flip function value calculation and corresponding logic circuit 33 is connected to the first barrel shifter 39 at the input end, and is connected to the input end of the final flip function operation and maximum flip function value search logic circuit 34 at the output end.

The final flip function operation and maximum flip function value search logic circuit 34 is also connected to the flip state update module 60 at the input end, and is connected to the input end of the flip bit logic circuit 35 and the flip threshold value selection module 31 at the output end.

The output end of the flip bit logic circuit 35 is connected to the input end of the flip state update module 60.

The first mutex or logic circuit 36 is connected to the output of the first barrel shifter 39 and the output of the flip bit logic circuit 35 at the input end.

The second mutex OR logic circuit 37 is connected to the flip bit logic circuit 35 and the data selection multiplexer 20 at the input end, and is connected to the data register 50 at the output end.

The second barrel shifter 38 is connected to the first mutex or logic circuit 36 at the input end and is connected to the symptom value register 40 at the output end.

During operation, the flip threshold selection logic circuit 31 selects the flip threshold E_th according to the number of input loops and the previous flip signal, the congruent signal, the oscillation signal and the maximum flip function value (max_En).

的翻轉函數值計算與對應邏輯電路32接收位移後的症狀值

，並如上述地產生

。 Symptom value

The flip function value is calculated and the corresponding logic circuit 32 receives the symptom value after displacement.

, and as aforesaid

.

的翻轉函數值計算與對應邏輯電路33接收位移後的症狀值

，並依公式(1)產生

。 Symptom value

The flip function value is calculated and the corresponding logic circuit 33 receives the symptom value after displacement.

, and according to formula (1)

.

及初次症狀值部分翻轉函數值

，並由公式(1)、公式(2)、公式(3)產生翻轉函數值

。所有位元的翻轉函數值產生後，既可用比較電路得知max_E_n。 The final flip function operation and maximum flip function value search logic circuit 34 receives the flip vector, the previous symptom value, and the partial flip function value.

and the initial symptom value partial reversal function value

, and generate the flip function value by formula (1), formula (2), and formula (3)

After the flip function values of all bits are generated, the comparison circuit can be used to obtain max_E _n .

，並決定翻轉位元向量每一位元為0或1。 The flip bit logic circuit 35 receives the flip threshold value E_th and the flip function value

, and decides whether to flip each bit of the bit vector to 0 or 1.

The first exclusive OR logic circuit 36 receives the shifted symptom value and performs an exclusive OR operation with the flipped bit vector to obtain the updated symptom value of the shift.

The second exclusive OR logic circuit 37 receives the data and performs an exclusive OR operation with the flip bit vector to obtain the flipped data.

The first barrel shifter 39 receives the symptom value and shifts it.

The second barrel shifter 38 receives the displaced updated symptom value and displaces it in the reverse direction. In this way, the second barrel shifter 38 generates an updated symptom value.

、

、

而產生全等訊號及振盪訊號。然後，翻轉狀態更新模組60把全等訊號、振盪訊號與

傳至位元翻轉及症狀值更新模組30。 As described above, the flip state update module 60 executes equations (4), (5), (6), and (7) to process

,

,

Then, the flip state update module 60 converts the congruent signal and the oscillation signal into

The data is transmitted to the bit flipping and symptom value updating module 30.

、

、

的長度皆為N，所以共需3*N位元紀錄其資訊。另外，在執行公式(4)、(5)、(6)時，需要較多的邏輯閘數完成運算。因此，在此提出僅儲存部分的翻轉向量，並調整公式(4)、(5)、(6)以達到降低記憶體空間(memory)、降低邏輯閘數(gate count)、獲得更好的時序(timing)與功耗的優點。 Three flip vectors

,

,

The length of is N, so a total of 3*N bits are needed to record its information. In addition, when executing formulas (4), (5), and (6), more logic gates are required to complete the calculation. Therefore, it is proposed to store only part of the flip vector and adjust formulas (4), (5), and (6) to achieve the advantages of reducing memory space, reducing logic gate count, and obtaining better timing and power consumption.

First, change the representation of the flip vector. Figure 3 shows a vector F, with a length N of (q+1)*w in accordance with the data transmission width W. In this embodiment, W=256 bits. Referring to Figure 4, the flip vector is cut into multiple units, each unit has 256 bits, and the address is defined as the number of 256 units. Therefore, each unit has two characteristics: address and binary sequence.

F ={ f ₀ , f ₁ ,..., f ₂₅₅ , f ₂₅₆ ,..., f ₅₁₁ , f ₅₁₂ ,..., f ₇₆₇ , f ₇₆₈ ,..., f _{N -1} }.

After rewriting, F ={ F ₀ , F ₁ , F ₂ ,..., F _q }, F ₀ ={ f ₀ , f ₁ ,..., f ₂₅₅ }, F ₁ ={ f _1＊256 ,..., f _2＊256-1 },…, F _q ={ f _{q ＊256} ,..., f _{( q +1)＊256-1} }. F ₀ to F _q are all binary sequences, their width (or length) is 256, and their subscripts are the addresses of each binary sequence.

為(T ₀)次 遞迴翻轉向量的5個位址，

為 (T _-1)次遞迴翻轉向量的5個位址，

為(T _-2)次遞迴翻轉向量的5個位址。其對 應的五個二元序列分別為

,

與

。

皆是256位元的二元序列。 Referring to FIG5 , the addresses with flipped addresses and their corresponding flipped binary sequences are recorded. In this embodiment, L=5. The superscript symbols ( T ₀ ), ( T _-1 ), ( T _-2 ) are used to represent the results of the T _0th and the previous two recursions.

The 5 addresses of the ( T ₀ )th recursive flip vector,

The 5 addresses of the ( T _-1 )th recursive flip vector,

are the 5 addresses of the ( T _-2 )-times recursive flip vector. The corresponding five binary sequences are

,

and

.

They are all 256-bit binary sequences.

Based on the structure of flipping addresses and flipping binary sequences, the patent replaces formula (4) with the following formula (a):

For formula (5) and formula (6), first determine whether there is duplication in the position. Define the intersection function intersection (A,B)=A∩B.

與

中，對應addr={d ₀,...,d _k }位置的二元序列為：

Respectively in

and

In , the binary sequence corresponding to the position addr ={ d ₀ ,..., d _k } is:

Substitute formula (b) for formula (5) and replace formula (6) with formula (c):

Using AWGN error channel to simulate decoding, the results show that the decoding codeword error rate (FER) effect is the same as that using formulas (4), (5), (6), and (7).

At least two sets of previous flip vectors can be used as the basis for the flip state. If two sets of previous flip vectors are used, the oscillation signal 2 is 0.

的翻轉函數值計算與對應邏輯電路32及33症狀值

的翻轉函數值計算與對應邏輯電路33被描述為2個邏輯電路，但實務上它們可被整合為一個邏輯電路。 Since the input register 10, the symptom value register 40 and the data register 50 store different data, they are described as three registers, but in practice they can be integrated into one register.

The flip function value is calculated and the corresponding logic circuit 32 and 33 symptom value is calculated.

The flip function value calculation and the corresponding logic circuit 33 are described as two logic circuits, but in practice they can be integrated into one logic circuit.

The above is only to describe the preferred implementation of the present invention, and is not intended to limit the scope of the present invention. Equal changes made by ordinary technicians in the technical field based on the above embodiments, as well as changes known to technicians in the technical field, are still within the scope of the present invention.

10: Input register

20: Data selection multiplexer

30: Bit flip and symptom value update module

40: Symptom value register

50: Data register

60: Flip status update module

70: Decoding termination module

Claims (2)

A fast decoder for a quasi-cyclic low-density parity check code comprises a register (10, 40, 50), a data selection multiplexer (20), a bit flip and symptom value update module (30), a flip state update module (60) and a decoding termination module (70), wherein: The register (10, 40, 50) receives and stores code words, symptom values, flip vectors, and flipped data; The data selection multiplexer selects the register (10, 40, 50) to receive the codeword or receive the flipped data and transmits it to the bit flip and symptom value update module (30); The bit flip and symptom value update module (30) receives the symptom value, the codeword, the previous flip vector and flip state related signals, and generates a flip vector, flipped data, and an updated symptom value, and transmits them to the register (10, 40, 50) for storage; The register (10, 40, 50) transmits the flipped data to the data multiplexer (20) for selection by the data multiplexer (20); The register (10, 40, 50) transmits the last flip vector and stored symptom value to the bit flip and symptom value update module (30); The flip state update module (60) receives the flip vector of each bit flip and symptom value update module (30), obtains a congruent signal and an oscillation signal after calculating with a set of previous flip vectors, and generates a flip state signal after comparing with at least two sets of previous flip vectors, and transmits the flip state signal to the bit flip and symptom value update module (30); and The decoding termination module receives the sum of the symptom values from the register (10, 40, 50) and adds the recursive number to generate a decoding status output signal. A fast decoder for quasi-cyclic low-density parity check codes as described in claim 1, wherein the flip state update module (60) uses part or all of each set of previously flipped vectors to segment the vectors in the form of addresses and binary sequences, and compares several addresses with their binary sequences respectively, thereby obtaining the congruent signal and the oscillation signal and determining the flip state.

Images