TW201019608A - Decoding method and system for low-density parity check code - Google Patents

Abstract

A decoding method for LDPC code, which comprises steps of obtaining a set of parity-check matrices of a set of block codes; obtaining an identical parity-check matrix from the set of parity-check matrices; dividing the identical parity-check matrix into an odd identical parity-check matrix and an even identical parity-check matrix, wherein the odd identical parity-check matrix being composed of odd rows of the identical parity-check matrix, and the even identical parity-check matrix being composed of even rows of the identical parity-check matrix; and decoding the set of block codes basing on the odd identical parity-check matrix and the even identical parity-check matrix.

Description

The present invention relates to a quasi-cyclic low-density parity-check (QC-LDPC) decoding method and system, and more particularly to a fast A method and system for decoding a quasi-cyclic low-density parity check code. [Prior Art]

In quasi-periodic low-density parity check (QC-LDPC) codes, H. Zhong and Τ zhang in April 2005 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I: REGULAR PAPERS, Vol. 52, No. 4, pp. 766-775 The block low density parity check (Block-LDPC) code disclosed in "Block-LDPC: A practical LDPC coding system design approach" can obtain good error correction performance and is suitable for implementation of Very Large Scale Integrated Circuit (VLSI). . Block Low Density Parity Check Code) χ (4)) The odd check matrix (PCM) is constructed by the right cyclic shift form of the 2 X ident identity matrix and the zero matrix. LMPD, combined with the concept of row grouping, column grouping, and column sum, is well suited for block low-density parity check codes, where block low-density parity check code-a block line is treated as a horizontal layer. The low density parity check code in the ieee 802.16e (WiMAX) standard is a block low density parity check code. The parity check matrix of the block low-density parity check (quasi-period low-density parity check) code of the code rate Rc in WiMAX is represented by a matrix from "," where Mmx沁, and #=zx%. Then, in the parity check matrix H, there are one row and one row, and the block column. Therefore, the parity check matrix 构 is composed of ...% sub-matrices, and the size of each sub-matrix is (4). The parity check matrix 建立 is established based on a basic matrix Hb. In the basic matrix &, each 〇 is replaced by a (four) zero-order matrix (zero matrix), and each 位于 at the position of (i, j} is replaced by a (1) 201019608, matrix (circular matrix), The above w-cycle matrix is obtained by cyclically shifting the w-unit matrix to the right (4) column, (10), ..., where the pool is determined in the WiMAX standard. For the low-density parity check code of (23〇4, 1152) , Μ=1152, Ν=23〇4, ζ=96, Μρ12,

Nb=24. ® 1 reveals a block-type parity check matrix of low-density parity check codes Η ' where the number shown in the i-th row of the i-th row is the heart, (d). In the block type parity check matrix 揭示 disclosed in Fig. 1, we can replace each of the blank portion and the square portion of the digital portion with a ζχζ zero matrix and a non-zero periodic matrix right cyclic shift. The periodic matrix located in the i-th block row and the _th block column is obtained by cyclically shifting a Z X z unit matrix to the right, and by man and column. It should be noted that the last 11 block columns of the parity check matrix H form a double diagonal structure. In WiMAX, the low-density parity check codes of all code rates Rc have the same basic matrix Hb, but they have different expansion factors z and different shifting indices p(/,; Heart, z). The shift indices 〆u, and c, z) are calculated according to the following formula: p(i,j,Rc,z)= p(i,j,Rc,z = 96)z 96 '

In WiMAX, 'four encoding rates (Rc=i/2, 2/3, 3/4 and 5/6) and 19 code lengths (z=24, 28 '32 '..., 96) are disclosed in the following sections. 16: Air interface for fixed and mobile broadband wireless access systems amendment for physical and medium access control layers for combined fixed and mobile operation in advantageous bands, IEEE P802.16e-2005, 2005. Further, the basic matrix 111) and p(i, _/, /ic, z = 96) are also disclosed in the above-mentioned same publication. Several methods, such as the TPMP-Two Phase Message Passing algorithm and the LMPD-Layered Message Passing Decoding algorithm, are used to decode the block low-density 201019608 code defined by WiMAX... In general, the hierarchical information transfer decoding algorithm has a small storage size and a low complexity 4H mode compared with the two-phase information transmission method. In addition, the 匕 layer information transfer decoding algorithm can obtain about twice the decoding convergence speed compared with the two-phase singular algorithm. Because the hierarchical information transfer algorithm is more advantageous than the two-phase information transfer algorithm, most _WiMAX low-density parity check decoders rely on hierarchical information transfer decoding algorithms. Ο 于 In the two-phase information transmission algorithm, the training indicates that the point is checked from the kth iteration! From the node to the bit node (c2v) information, and (10) represents the set of indicators including the check node, the bit node of point i. Similarly, the _ table is not in the kth iteration from the bit node 』 to the check node 丨 bit node to the check point (V2C) H and /e[y] represents the metric set of the check node including the bit node . A horizontal layer contains a set of rows of parity check matrix H (a set 〇f rows). In each horizontal layer, the column weight (c〇lumnweight# ^ or , in order to check the node operation is performed for each horizontal layer instead of the entire parity check matrix H in the two-phase information transfer algorithm, layering The information transfer decoding algorithm is the same as the two-phase information transfer algorithm, and the updated after-the-fact probability (APP) is transmitted between layers. For each check node in a single horizontal layer, the adjacent bit 1 node _/e/ sW, according to the following equation (1), 事, after the iteration according to the following equation (APP), 乂7[幻=沁丨[幻] and [免免]=心[k] - -1 ]. Qji [^] = Ay [A: -1] — Rj [k — 1] (1) (2) W = β, #] + = 1] + δ (3) General 'Based on layered information transfer decoding The decoder has two memory banks and Μ5Λ for 5 201019608 storage and eight values respectively. The concept of the "LDPC code construction with flexible hardware implementation" of Proc. IEEE Int. Conf. Commu, Anchorage, AK 2708-2712, published by DE Hovevar on May 11-15, 2003, is It is only necessary to read the value of Λ) [Λ: -1], which is defined by 乂y = ln(Pr(v7. = 0 丨a ) / Pr(v; = 1 丨3^.)) The channel value and the sum of the check node to bit node (C2V) information, and a value of Α[*-ι] are calculated in the kth iteration. The value is stored in the memory bank and initialized to 〇. Values with the same i are stored in the same address of the memory group so that we can access these values simultaneously. The memory group is used to store the value of Λ; (or APP) defined in equation (3), which is initialized with Α where seven are the channel values of the bit node V/. Since the low-density parity check code for WiMAX is a block low-density parity check code, we can use the parity check equation defined by one block row of the parity check array H as one of the component layer information transfer decoding algorithms. Floor. Since the column weight of each column in each block row (layer) of the parity check array is 〇 or 1, we can use one processing unit in parallel.]: Hovevar on May 11, 2003- The concept of row grouping used in the "LDPC code construction with flexible hardware implementation" of Commu, Anchorage, AK 2708-2712 is calculated in 1S. Since the z-check node processing unit can perform parallel operations when the memory is accessed without hazard, the parallelism of this structure is z. Since the number of decoding cycles is roughly equal for all z, the throughput of the decoder will be roughly proportional to Z. If we use the maximum parallelism of z:96 in the numerator, when we use this decoder to decode the low-density parity check code of z=24, most of the hardware resources in this decoder will be in Idle state. 201019608 Fine-grained decoding [invention], provided by — — 种 种 种 低 低 低 LDP LDP LDP LDP LDP LDP LDP LDP LDP LDP LDP LDP LDP ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ ϋ The embodiment provides - an array of low-density parity check codes; a parity check matrix of a series of block codes from a series, ::r, and a parity check matrix to obtain a parity check matrix; The matrix is divided into odd-even parity check matrix and even-odd odd-equal r', where the odd-even parity check matrix is composed of an identical parity check matrix (10)-an even-even parity check matrix from the parity check matrix. Check the even money (four) listening to the parity and other parity = the even number of rows of the check matrix. The decoding system includes a plurality of post-event probability values corresponding to the block columns of the first-th order; the complex number of the i-th plurality of check nodes to the plurality of bit nodes is connected to the processing device of the point information '· and the value The electrical handle H and the second memory group decode the low-density parity check code of the 201019608 number of block codes according to the parity check matrix such as the odd parity check parity number. The present invention divides the parity check matrix into odd and even parity check matrices for hierarchical information transfer decoding algorithms, and the convergence speed using the present invention is faster than using a two-phase information transfer algorithm. The above and other objects, features, and advantages of the present invention will become more apparent and understood. [Embodiment] ❹ In the real example, we use ///〇) to represent a matrix including the p, p(z), (p + 2z) of a parity check matrix (PCM) H, And the (p + (Mb-l) z) line, its household: like, 2i. Moreover, we use can) to represent a non-zero column in the set, which indicates the matrix coffee. For (4) to one, we remove all the zero columns in · to get a ^ please, matrix open (9). Therefore, R(p)| = M. From the quasi-periodic structure of the parity check matrix H, the matrix 仏(9), the wide 0'1, 2"..々1 is the column, the (〇) column interchange form, and for /^〇, U,··.,:- 2, S, (p + l)= w {q \g-Jz = ik + l_ jz) m〇d ^ + ^ ^ (4). For example, Tian ^(9) 'smoke,}, then &(1)= {1S , 44, 62, 丨. We found that the collection 'P(U,2,·..,,]] is not the same. In addition, for the calyx 12, one-i, the order) n[u;忉 is an empty set. Obviously, and % <<iv. Low-density parity check (LDPC) code c is formed by the coding bits indicated by the set-can-linear block code. Matrix object (four) block code - Parity check matrix. Because the matrix (10) - constant parity check moments are replaced by one of the columns: the equation can be used to decode the linear block code c, (9) by using a parity check matrix such as a value. By continuously decoding the linear block 4|c(9), c(i), .., and imprint]) perform decoding of low-density parity check code C. We first consider the low-density parity check code c among the chore-horse bits indicated by the set Channel (reliability) value while decoding linear region 201019608 block code (9), then low Among the density parity check codes c, the channel values of the coded bits secreted by the set, and the extrinsic value obtained by decoding the linear block code (9) are decoded to decode the linear block code C/1. After the block code c&2), we decode the linear block code. Such a round for the linear block code (4), /> = 〇, 1, 2, ..., Bu 1 decoding, is called for low density Parity check code (: decoding one global (Cai (4) iteration. After linear block and (iv) decoding, we then decode linear block code c, (9), etc. in linear block code 0/(9) decoding, because for P 0,1,2,...,z 1 $(9) Gate [LU〇Jstp $(/)]矣卢, we can use the solution line block code (10)"々 when we solve C,〇) Extra value (extrinsic river). Because in the decoding of the linear block code (9), we can use the other linear block code C/C/) in the same global iteration, the extra value obtained by the corpse p decoding, so The decoding method provided by this embodiment has a faster convergence speed than the two-phase information transmission algorithm used in the prior art. The method will be described in detail in the following paragraphs. For the (2304 ' 1152) low-density parity check code, we find that the parity check matrix A has a - (four) special structure, and most of the columns of the parity check matrix have weights. Moreover, the weight of the last π column of the parity check matrix Α is 2. In addition, the identical parity check matrix rings the last 11 columns to form a double diagonal structure. And sub-groups - an even layer and an odd layer. In other words, 'we will blame the parity check moment and divide it into two matrices, including the odd-even check matrix & and the odd-even parity check matrix Α and Α are all dimensions /2 χ 〃 And consisting of odd and even parity check matrices, odd and even rows*. Since the transparency check is turned to the double diagonal structure of π, the additional value obtained in the linear block code gamma decoding can be used based on the odd number based on the even parity check matrix (or the odd parity check matrix 乂) The decoding of the linear block code ς ω of the parity check matrix & (or even parity check matrix Α). Because the parity check matrix 奇 of odd and even odds and the 201019608 weight of 4 are thus decoded to effectively execute the linear block code (10) ^^^^^ thus has a linear iteration of the linear block code rp^ Jp^, ° The class of the algorithm is called even-odd information transfer decoding (EO-MPD). 1.5 and 2 two orders / 1;,, - The case of human iteration is called EOE-MPD and in other words, the 'linear block stone horse' E〇E_MPD by continuous 'new material inspection material A, odd materials Even check the matrix &, and then make the singularity check to turn W guess. Among the three methods, the EO MPD (EOEO-MPD) method can obtain the worst (best) error performance, but its

The minimum (maximum) number of check node operations as defined by equation (2) above is required. We will introduce the decoding architecture using the (2304,^) low-density parity check code in the following paragraphs. ρ疋义屯和尽? is the number of quantization bits used to represent ... and heart, respectively. After the event, the rate of the tongue has been restored to the body group MBA including 'z zBa storage, respectively, in tons, j = 〇, j,. The memory block MB! is composed of 單埠FIF〇s. Each block of the store can be used to store the value of a block corresponding to the parity check order. Eight j ' j ~ 〇, 1".., z - 1 value is stored in the memory block ^ ^, ~ seven, j = 〇, 込 · · ·, z - 1 value is stored in the memory area In the block ^^, and so on. When decoding ci(P) ' P =0, 1,...i, we must access eight, j4(p) from the memory group ΜΒλ. Figure 2 reveals How does the C2R (R2C) network read from the memory bank MBj? The number of edges in the \°C2R (R2C) network is equal to the number of equal parity checks, the number of 1s in the matrix 。ι. As mentioned above, the identity The number of 1 in the parity check matrix 4 is much smaller than the number of 1 in the parity check matrix 。. For the (2304, 1152) low-density parity check code 'in the parity check matrix and the parity check matrix η, respectively, there are 76 1 and 7296 1. Therefore, the winding complexity of the C2R (R2C) network is significantly reduced in the above architecture. By using {八山4(0)丨, {八如31(1)丨,..., {8^81(2-1)丨, successively decode 201019608=block code C/(〇), C/(1),..., (4), respectively, to perform the above-mentioned uncutting

+ ^ ^s/(p + 1)#s,p)<ra^ J is expressed in the above equation (4). D! The parity check matrix disclosed in Η: to obtain s, (9) = {12, 43, 61, ...}. Using equation (4) as in (9), we can wait for {13, 44, 62,...}. Similarly, we can get 3(8) -1 〇 ^ J ^3» ··· >z

Because the maximum row weight of the parity check matrix ( (r〇w weig_ 7 ', the body group MBR includes Mb blocks, each block size is Ζχ (7 Μ, this memory module mbr# is initialized to G and used to store information (4) value: The body group mbr is composed of a single buffer register. Since the information h is properly stored, only one cycle is required to read (write) from the memory group MBR. The value of the information Rij., 1 Ο

As previously mentioned, the EOE-MPD utilizes the last 丨 weight of the identity parity check matrix H to be 2, and the last U column of the parity check matrix Ηι forms a double diagonal structure to increase the (iv) speed. We turn off the decoding architecture of the 3 towel to effectively execute the EOfjypD of the linear block code cl(P), p = 〇, 1, ..., z_ ! The decoder 30 in Fig. 3 is for continuously decoding the linear block codes Ci(9), Ci(1), ..., c(z l). For the parent check node i of the identity parity check matrix, we divide the set into a set I ' where IB[i] includes the last two bit nodes (coded bits) of the constant parity check matrix % and U^iRLi \iB[i]. We define, =UylB[i], in the above example, 丨Ibt丨 For each bit node jelBT, we have Aj[k]=4+RjW+Ri[k], where 〇·, deli]. Further, if i' is an odd number, i is an even number. Therefore, we calculate the channel value according to ;^ = Λ>]Ά]-Ρ^Η because most of the even parity check matrix He has a weight of 1, and #CVMU (check node to bit node information update) The cell is labeled as CVMU even layer 324. CVMU even layer 324 11 201019608 According to the constant parity check matrix % of the 铋 铋 , , , , , , , , , , , , , , , , , , , , , , 阵 恒 ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml ml _ V2C 勒,1中 / ” T ri I use ^ w= λ) + RHk] to calculate the odd-numbered rows i of the odd-trace matrix Hi, such as the odd-numbered odd-numbered CVMU | The other parts of the HCV bribe layer 326 ^ * ❹ ί t 'CVMU module includes a set of C_ odd layer 326 and a set of CVMU 4 ^ CVMU overview of its towel - part of the calculation and point to the side of the check node -_ The additional value, wherein the bit = corresponds to the _ column of the parity check scale of the even button, the other bit node of the CVMU module to the plurality of second of the associated check node. := 2, the Another bit node corresponds to Qi Qing's parity check. For all JsiBT, we use v 7c + Rj[k] to calculate v2c information Qjk] /, medium I'ielc[j]. > It is an even number. Because the value is equal to the parity check, the last few columns in H form a double diagonal structure, which is used in the general _ and the node 'and root #健(四) odd check matrix% (odd number) The parity check matrix H.) and the % (Q) obtained in decoding the linear block code Cl(6) can be used for & odd parity parity check matrix H. (even parity check matrix HJ and decoding c丨(6) The outputs of these CVMU units 324 and 326 are fed back to the unit of difference calculation (DC) 328 to calculate the heart and heart. The picture of the CVMU unit and the DC unit is disclosed in Figure 4 and Figure 5, respectively. The CVMU unit 40 includes an APP-R module 400, a ml-m2 selector 420 and a B_part 12 201019608 R and a Q calculator 440. A DC unit 50 constitutes an A-part register 500, and an R register 540. ' ml-m2 selector 520 and i? and Λ/? calculator 560. The detailed steps are as shown in Fig. 6 and are described below. Stage 1: In the cycle 〇 ΑΡΡ memory group ΜΒ λ3 〇〇 Read the associated VIII > -1 value and use the column-to-row module (C2R) 32() in the period 而 in the line base form: configure the relevant \b1] value. In the period 1 towel, The fine-grain check node-to-bit node information read module (R read) 322 reads the associated Rij[k-1] and Rjk-l] values from the R memory bank. ❹ -^ Section 2: For In constant Each of the even rows and each bit node jelj in the parity check matrix is calculated by the APP-R module 400 in cycles 2, 3, and 4 according to the above equation (1). Then, using the module of the ml_m2 selector, the values of the week = , ^, ^ and ". secret, ^, U and U are stored in the DC unit 5 by the π stage and are stored in the A part register 500. In cycle 5 'we use the module of the selector to calculate 吼m2, Jin,, andJm2. In steps 3, 4 and 5, execute these in steps ', for each bit node je(10), we also use The App-R module 400 Ο "'ΐΜϋ["ΐΗ'#·ΐ]=9^ ' ❹# is performed in the step ical of Fig. 6, and the towel is executed. Note that all of the πα used for Phase 3 are calculated in the above steps. In cycles 6 and 7, use the ^ ieu*] ° node (four) to calculate Q [k in cycles 5 and 6. 1 and the parent bit, L, and the sound obtained in phase 2, and 13 201019608 at all, calculate Q#]=\+ Rfj[k], i, eic[j]. Stage 4. This stage relates to the operation of the DC unit 5〇 disclosed in FIG. For constant!, look up each odd-numbered line in the matrix H1, and use the R and the new calculator 560 to calculate the ringing in the cycle mountain. Similarly, for the parity check matrix η such as 悝, each even row 丨 ' Using ml_m2 selector 52〇, update ml, m2, jml and u in cycle η, then calculate r system and phase 5 in cycle u: in cycle 13, use check node to bit node information to write module ❹ ( R is written 332 to directly write the correlation value of Mk] to the R memory bank mbjo. For the calculation of eight, the row-to-column module (R2c) 33〇 is used in the period 13, and the correlation values of ΔR^k] and ArJIc] are arranged in the column basic form. In the period μ, for each bit node jelji,,], calculate A[k], which is done with eight doubs _1] + ^]. For each bit node jelB[i], we can also calculate Aj[k], where iieic[j], using A[k]= + △ Rjkj+Aiyk]. 'In order to increase throughput' CP Fewer, MF Flanagan and A. d. Fagan, IEEE Tr_. Cinmits SySt· I, Reg, Papers, Vol. 54 No. 10, 2240-2250, published in April 2007 Versatile variable me LDPC eodee 〇architecture" 'The author reveals that two sets of codewords can be solved simultaneously to improve throughput. In the present invention, we propose to use a five-stage pipeline architecture to increase throughput. The scheduling is disclosed in Figure 7. Since it uses five decoding stages to get the Δ_ for '[k], we need several five-stage registers to store Λ [ku level register Ui,i =0, 1,..., 4 said. Figures 8A through D illustrate the contents of (iv) several storage areas obtained by dividing a memory block into a memory ship and a scratchpad file in decoding. The storage area is composed of FIFOs in this embodiment, which will hereinafter be referred to as FIFOs. Further, each register file includes at least one/scratchpad. Initially, the lengths of FIFO-O, FIFO-1 and FIFO-2 were 47 (12_61+96°), respectively, 14 201019608

31 (43-12) and 18 (61-43). In the phase A, A61[k-1], A12[k-1] and A43[k-1] required for linear block code Ci(〇) decoding are from FIFO-O, FIFO-1 and FIFO-, respectively. Read in 2. A61[k-l]'A12[k-l] and A43[k-1] are also stored in phase 1 and U0 of REG1, respectively. In phase 2, Aw[k-1] ' Λ13[Ιί-1] and Ajk-1] required for linear block code Q(l) decoding must be read from the FIFOs and should be stored in the scratchpad. U0, so A61[k-1] 'Adk]] and Ajk-i] move to U Bu in stage 5, A61[k-1], A12[k-1] and A43[k-1] in "U4" And the difference from the corresponding C2V information, that is, AR, is added to generate A6i[k], Al2[k] and A43[k], which are respectively written to FIF〇2, FIFO-O and FIFO-1. Since all the lengths of the memory blocks mb# FIFO_0, FIFO-ι and FIFO-2 are greater than 5, these FIfqs are not empty during the five-stage pipeline decoding process. Therefore, there is no memory access barrier in the memory block. Now consider the memory block (4), which is dangerous when accessing the memory. Touch, in the memory block MB〗. The FIF 〇 _ 〇, FIFO-l and FIFO-2 lengths are 42, 52 and 2, respectively. The length of FIF〇 2 is less than 5. This means that FIFO-2 will be in a valueless state. In addition, during the five decoding stages, we have to update the number of bits of the node & For this problem, p will introduce the solution below. 9A reveals the knot of the memory block. In addition to the following different 'memory blocks _. The structure is the same as the memory block. Block (4) and _. In, and FIF (the input of M is derived from the output separately. However, in order to avoid the occurrence of FIF in the pipeline decoding, the input of FlFa2 in the memory block_FlFa2 is output from FIFO_0 instead of ^ In the memory block MB丨 and MB?, REG0, REG1 and REG2 = input is input, FIF〇_2 and touch data to one input pipe. = T 'J·11 and U2 # are decoded in five stages At the time of decoding only the structure disclosed in Fig. 9A, we can obtain the contents of fif〇s and the scratchpad in the valley shown in Fig. 15 201019608 9B to G. Read out from FIFO-Ο in stage 0' In stage i, Λ7 [μ is stored in U0 in FIF〇_l and REG2 to avoid the occurrence of FIF0_2 valuelessness. It is read from FIFO-2 in phase 2 and stored in 拙(1) in phase 3.阶段. In stage 5, corresponding to Λ?2, such as AR72(9), is available, and is added with '[Μ] to produce a temporary ΑΡΡ λ„[k]. Temporary APP 八72 [k] in stage 6 It is written to U3 of REG 1. In stage 7, a new Δ/? corresponding to Λα, that is, δ/?72(2), is available, which is added to the temporary APPA72[k] to produce the final App^w . As mentioned earlier, four code rates (where =1/2, 2/3, 3/4, and 5/6) and 19 yards are detailed in WiMAX (#=576, 672, 768,..., 2304) The size of the sub-matrix can be selected from 24 X 24 to 96 X 96. The size of the basic matrix Hb for the code rate and the size of the parity check matrix Η are [(i_Rc)24] X 24 and [(1- Rc)24z] X [24ζ]. The number of connections of the bit nodes (or the weight of the parity check matrix )) is 2, 3, 4, and 6. For a code rate of 1/2 and a code rate of 5/6 The low-density parity check code checks the maximum number of connections of the node (or the parity check matrix Η the maximum row weight) of 7 and 2 〇 respectively. The design-decoding architecture of the WiMAX mosquito seam density check code is a huge Challenge. Now we reveal how to modify the previous pipeline architecture to support the low-density parity check code decoding defined by 〇WiMAX. If the memory banks mbr and μβλ are properly configured, the above is used for (23〇4, 1152) low-density parity check. The decoding architecture of the code (ζ=96) can support other low-density parity check codes with a rate of 1/2 in WiMAX. The calculation part, such as the CVMU unit, does not need to be changed. See, for the (23〇4, 1152) low-density parity check decoder, the memory group mbr can support other low-density parity check codes with a code rate of 1/2. Now we will not disclose how to configure the memory bank μΒλ. Support for other low-density parity check codes with a code rate of 1/2. Use the set to call: ^... mountain grab (10) yield rate low density parity check the non-zero row of the jth column in the base matrix Hb, where d (jR ) is the basis 16 201019608

The column weight of the jth column of the matrix Hb. This is expressed for all ζ·e hearts, z) 2 0. Since the code rate is that all of the low density parity check codes have the same basic matrix Hb' for each memory block, the number of FIF 〇s is the same for the same low rate parity check code of the same code rate & Assume 沁. , :), Re, Z) >...〉^^), 〗, ^). The length of MBk FIF〇 in the low-density parity check code is [Ρ(ΐ〇,·Λ,ζ)-成,以,ζ)] [Ρ(1,^.Ζ) - p(i2J,Rc,Z ) ], ..., [ -p(WiJj^z) IP(hj,Rc,z ~96 ~ [P(kaiU-i,j,Rc,z)-卩(1.,:|_,11( :,2)+2].According to the rush, the price, the illusion =^^1^1^^£ . |_ 96 P\}y 〇乂 foot ^ = 96) 'We found that if we choose each based on z=96 The code length of the FIF〇, then these FIFOs only need to be partially modified by the APP access unit, and can be set to support other code lengths. For the multi-rate capability, we perform the following in the memory group and the slave. Modify. The number of each FIF0s should be dirty ^ dv (j RJ, and the length of each storage area of each memory block (FIF〇 in the above embodiment) can be increased to match the needs of all these bit rates. In the (10)4, (1)2) low-density parity check decoder memory module (10), consisting of 12 blocks, each block containing ζ 7 (7Br) memory. For multi-rate capability, memory The group ton is also made up of j © into 'but each block contains 8BJ storage. The code rate is 1/2 = degrees Even check the decoder, a block (zX (8Br) storage) is used to store the C2V information corresponding to the block row of the parity check matrix 。. Low =, degree parity check decoding in the code 5/6 H, the three-sided block locator stores the C2V information corresponding to the block row of the parity check array. Based on a similar method, we can configure the memory bank to support the code rate and the code rate to correct the density. Parity check Τ. In our multi-code rate and multi-code-length decoder, the memory group·a constitutes 24 memory blocks, each of which constitutes 2 to 6 library areas, and the memory group you & consists of 12 96 X 40 memory blocks. 17 201019608 Now we show how to configure a CVMU unit for a low density parity check decoder with a rate of 1/2 to support a low density of 5/6. Parity check decoding ^. The CVMU unit is responsible for the calculation of the information about the line of the constant low-density parity check matrix H. Since the number of lines of the constant low-density parity check matrix H is 1/2 for the code rate and the code rate is 5 The low-density parity check code of /6 is equal to 12 and 4, respectively, and the code rate is 1/2 and the code rate. The 5/6 low-density parity check code has 12 CVMU units (CVMU-1/2 units) and 4 CVMU units (CVMU-5/6 units), respectively, because of the low-density parity check for a code rate of 1/2. The maximum row weights of the parity check matrix 低 of the low-density parity check weight of 5/6 are 7 and 2, respectively, so we can combine 3 CVMU-1/2 units to form a CVMu_5/ 6 units. The configuration of the CVMU unit for the CVMU-5/6 unit is shown in FIG. Assuming the parity parity check matrix H, the weight of the ith row is 20. We will write 20 non-zero |(^|, divided into three parts into three units in the i-th row corresponding to the parity check matrix 4'. With the appropriate hardware scheduling, it will be possible in 7 cycles. The minimum and minimum values of 2〇|Qj| are obtained. Based on a similar method, we can configure the CVMU unit for the low-density parity check decoder with a code rate of 1/2 to support the code rate of 2 /3 and a low-density parity check code with a code rate of 3/4. D A decoder based on overlapping information transfer decoding (PO-MPD) at c _H Uu, S.-W. Yen, C.-L. Chen, H.-C. Chang, CY Lee, Y._s·Hsu and S._J. Jcm in March 2008 IEEE J. Solid-State Circuits, Volume 43, 684-694 K'An LDPC decoder chip based on self- The routing network for IEEE 802.16e Applications" is incorporated herein by reference. From the simulation, we found that the EOE-MPD based decoding was performed with Nit = 12 to obtain TPMP with a team = 15 LMPD, Nit = 30 , Nit = 20 P〇-MPD similar BER. at T·Brack, M. Alles, F. Kienle and N. When on September 11-14, 2006

Proc. IEEE Annual Intema-tional Symposium on Personal Indoor and 18 201019608

Aiobiie Radio Commmiications (PIMRC 2006), IMsinki, Finland "A synthesizable IP core for WiMAX 802.16e LDPC code decoding-Comparatively, the code length parameter has only a slight impact on the throughput of our decoder. In addition, the WiMAX decoder achieves a throughput of 30 Mbps required by the WiMAX system specification with a smaller parallelism. While the present invention has been described above in detail, the present invention is not intended to be limited thereto, and the present invention may be modified and modified without departing from the spirit and scope of the invention. The scope of protection is subject to the scope of the patent application. In addition, any of the objects or advantages or features of the present invention are not to be construed as limiting the scope of the invention. In addition, the abstract sections and headings are only used to assist in the search of patent documents and are not intended to limit the scope of the invention. BRIEF DESCRIPTION OF THE DRAWINGS Fig. 1 is a schematic diagram of a block type parity check matrix ( of (2304, 1152) low density parity check code. Figure 2 is a block diagram of a memory access from a memory bank from a memory bank. 3 is a block diagram of a low density parity check decoder in accordance with an embodiment of the present invention. 4 is a block diagram of a check node to bit node information update (CV3VRJ) unit in accordance with an embodiment of the present invention. Figure 5 is a block diagram of a difference calculation (DC) unit in accordance with an embodiment of the present invention. Figure 6 is a diagram showing the steps of decoding hardware for a low density parity check code having a code rate of 1/; 2 in accordance with an embodiment of the present invention. FIG. 7 is a schematic diagram showing the steps of decoding p (0), p, 0, 1, 2, ..., and dice by using pipeline technique according to an embodiment of the present invention. 201019608 Figures 8A-8D are schematic diagrams of the operation of the memory block μβ°λ2 suitable for the pipeline architecture in accordance with an embodiment of the present invention. 9A to 9G are diagrams applicable to a pipeline architecture memory block MB according to an embodiment of the present invention. Schematic diagram of the structure and operation. Figure 10 is a block diagram showing the structure of three CVMU-1/2 units forming a CVMU-5/6 unit according to an embodiment of the present invention. [Main component symbol description] 30: Decoder ^ 40 : CVMU unit 50 : Difference calculation unit 300 : After-effect probability memory module 310 : R memory module 320 : Column to row module 322 : Check node to bit node Information reading module 324: CVMU even layer 326: CVMU odd layer 328: difference calculation module Ο 330: row to column module 332: check node to bit node information writing module 400: APP-R module 420 : ml-m2 selector 440: Part B R and Q calculator 500: Part A register 520: ml-m2 selector 540: R register 560: and Δ/? calculator 20

Claims (1)

201019608 VII. Patent application scope: 1. A decoding method for low density parity check code, comprising: obtaining a series of parity check matrix of a series of block codes; obtaining a strange parity check matrix from the series of parity check matrices The parity check matrix is divided into an odd parity check matrix and a parity checker, wherein the parity check matrix is composed of odd rows of the check matrix 'The even parity check matrix is checked by the parity check The even-numbered rows of the matrix are composed; and 该 the series of block codes are decoded according to the odd-slot check and the even-recorded keel check matrix. The step of decoding the series of block codes according to the odd-numbered parity check matrix and the even-numbered identical parity check matrix comprises: decoding the face block code according to the even parity check a number & value, and providing the third value of the third value to decode the blocks according to the odd matrix _ to decode the block codes using the first series of second parity check matrix to obtain -number Constant's value and provide the additional value of the second series so that the second series can be used according to the even code, and the uncut method as described in claim 2 (4) Even number of strange materials and odd material parity check _ and continuous transcoding of the system 4 check such as the section 1 ==; ^ 3 fall material m tilt includes a loose - that is, the point of the number of bit nodes of a set of one second The indicator is a slashing knife, a singularity, a singularity, and a singularity. The singularity includes a portion corresponding to the parity parity 21 201019608 ” column having the weight 2 of the bit node, and the first buckle The person set includes the other part of the bit nodes. (4) The method of solving the wealth described in 4 items, the mask of the series of nightmare codes is 'indicated by the second indicator sub-set', which is based on the parity check matrix such as the stable and the odd parity check matrix. Decoding 6. If you want to use the special _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ι人集' such that the second indicator sub-set includes a portion corresponding to a value such as a parity, a C-weight 2 of the bit nodes, and the first----the titanium-human set includes the bit nodes Another part. 7. If you apply for the code described in item 6 of Wei Wei, ==: and the parity check matrix of the Na, etc. = 2 2 Wei number parity check scale solution (4) Wei block code to obtain a = provide the first series The meal value is such that, according to the odd block code, the odd-numbered parity check matrix of the odd-numbered parity is used to decode the block codes to add an additional value of the second series, and the second series is provided. : Even check the code of the block - use = 8, as described in the patent scope of the seventh party, = etc. Checking the matrix and the even-sense and other odd-sense matrixes == odd number: the extra value of the two columns and the extra value of the second series are only part of the bit nodes on the parent block code and the indicator sub-set It is pointed out that it breaks the first 22 201019608 9. If the patent application is turned over, the solution method is used to decode the data. 10. A decoding system for low-density parity check codes. , which is suitable for decoding a fitness odd-riding surface with a 胄-parity check matrix, the parity check matrix can be divided into a plurality of block rows and block columns, and a constant check matrix is obtained from the parity check matrix, which can be divided into - An odd parity check matrix and an even parity check matrix, wherein the odd parity check matrix is determined by the odd row of the matrix, and the square parity check matrix is determined by the parity check matrix of the board The even number of lines and shouts, the decoding system includes: machine booth first - record (four) group 'the tearing should be in these blocks, a number of after the Eh, the body group 'storage from a plurality of check nodes to a plurality of bit nodes Multiple Checking the node-to-bit node information; and ^ τίϊ device, the electrical property is reduced to the first memory group and the second memory top number, the parity check matrix, and the even parity parity i matrix to decode the low The complex charm block code of the density parity check code. - ❹ = the decoding system of claim 10, wherein the processing sets the first memory group of the memory to be configured from the first rate value to the line-based form of the event value and the read event is - Check the #点至位元 node information reading module, two records == some check nodes to the bit _;- yuan, and the wire is connected to the column to the line module and the "information reading module to accept Line base form 23 201019608 The probability of the post-progress is like the "inspection of the position" of the point-to-bit node. The check nodes to the bit node information of the _-port P-knife π = two of the bit nodes to the check nodes The additional value of the plurality of first-column columns, and the bit node corresponds to the column-column, and the other part of the ^e-equivalent check element is used for calculation and output from the other-serving-- Single potential (four) - 卽 point to the additional values of the first series of the check nodes, and the other bit is equal to the parity check matrix - Ρ points correspond to the number of rides ο - difference calculation · 'its electricity Reduction to the interest update module, the difference calculation module includes at least = point to bit node The output of the information update module is calculated; out: = node information and - the new line basis form the probability value of the after-effects to the group, the power_to the difference calculation mode (four) = and = the form of the base form after the probability value Configure to one. a new post-event probability value of the haiy- § mnemonic group; and ❹ 2 ==== difference = and the polling node is a decoding system described in item 11 of the patent scope, wherein the first-memory memory area The block 'each of the first memory blocks stores the after-effect values corresponding to a partial block column. And the device building includes at least one register ^, Λ ^ - the fifth hidden & block Read the after-effect rate values. The decoding system of claim 1 , wherein the first memory 24 201019608 memory group includes: a plurality of first memory blocks, each of the first memory blocks corresponding to one of the plurality of memory blocks The block lists the after-the-fact probability values; and ", a plurality of register files, each of the register files includes at least one register and is used for storing the first s Taking the probability value of the event. 14. The decoding system of claim 13, wherein one of the first memory blocks corresponds to one of the register files, thereby Ο The after-effect rate value of the δ-remember block is stored to the corresponding one of the register. 15. The decoding system of claim 10, wherein the first group of memories is configured to decode the block codes in a pipeline manner, and the pipeline mode is divided into a predetermined number of stages. 16. The decoding system as claimed in claim 15 wherein the first memory group comprises: a plurality of first memory blocks, each of the first memory blocks being stored corresponding to one of the block columns The after-the-fact probability values; and the plurality of scratchpad files' each of the temporary register files includes at least the predetermined number of registers and for storing the after-sales machines read from the first-memory blocks The decoding system described in claim 16, wherein each of the levels is divided into a plurality of storage areas, wherein one of the storage areas is a storage area, and when stored in the destination storage area When the number of the rear machine is small _ a predetermined number, the stored value of the previous storage area in the storage area is read. The value of the event value stored in the previous storage area is adjacent to the point storage. The value of the after-sales value stored in the area, and the previous storage 25 Ο ❹ 201019608 and the temporary storage ^ ^ ^ ^ ^ _ stored in the miscellaneous storage area of the previous temporary temporary storage and . ° ° secret The output is stored in the temporary crying files < .. The existence of a temporary register (four) - the end = special paste: = = = first - record β plural number of memory blocks, each of these single block of these columns after the probability value, and each _ ^ And the second J corresponds to at least the same as the predetermined number of the highest column weights in each of the low-density checks; and the parity check matrix of the horse is used to include at least the scratchpad and the on f MU The probability value after the event. 2〇, as in the decoding system described in Item 18 of the patent application system, the memory group is a predetermined number sufficient to cooperate with the pipeline mode of decoding the block code in a pipeline manner. Second, the decoding system described in the second aspect of the patent, wherein the first plurality of first-story blocks, each of the first-memory areas only have the after-effect probability values of the blocks. And each of the two correspondences = blocks are divided into the predetermined number of storage areas, wherein the predetermined number of small = hidden area low density parity check codes corresponding to the parity check orders ^ ... the maximum column weights; In the same column, 26 201019608, a plurality of temporary storage series, each temporary temporary storage And for storing the predetermined number of rate values from the first = the second. The second memory block reads the after-effects [2, as described in the patent scope of the illusion, is divided into a plurality of storage areas Two Γ:Γ; when the number is less than the predetermined number, - the probability value after the event ❹: the fresh value, the cut (four) ^ stored in the 3 terminal library area stored in the secret rate value of the reading The after-the-fact probability 1 is one of the previous scratchpad files in the temporary file; and the dot-storing area point "= in the two temporary register files - the final memory reads from the destination storage area After the event, the file is accepted and stored.