Efficient encoding of IEEE 802.11n LDPC codes Z. Cai, J. Hao, P.H. Tan, S. Sun and P.S. Chin Addressed is the issue of LDPC coding for the emerging IEEE 802.11n standard. An efficient encoding algorithm is proposed. The algorithm is simple and easy to implement. The memory requirement is trivial. Introduction: Low density parity check (LDPC) codes, first introduced by R.G. Gallager decades ago and rediscovered by Spielman, Mackay and many others, can achieve very good performance when decoded with the belief-propagation (BP) or the sum–product algorithm [1, 2]. The remark- able performance of LDPC codes has positioned them as strong candidates for forward-error-correction (FEC) codes in many emerging digital communication systems, such as IEEE 802.16e [3] and IEEE 802.11n [4]. However, implementing LDPC codes in hardware is by no means a trivial task, even from the point of view of today’s VLSI technology. Many authors have addressed this issue for both encoding and decoding of LDPC codes [5, 6], e.g. structured LDPC is proposed to facilitate the hardware implementation with just subtle sacrifice of performance. An efficient encoding method of IEEE 802.11n LDPC codes is presented in this Letter. We show that encoding of IEEE 802.11n LDPC codes is very simple owing to the special property of the parity check matrices. It is done without reference to the code generation matrices. The memory require- ment is only the length of the codeword. Systematic encoding of IEEE 802.11N LDPC codes: an efficient encoding method: Given a (sparse) parity check matrix H, the goal of encoding is to compute the systematic codeword c from the input sequence m. The encoding for LDPC codes has been investigated by many researchers [6–8]. Owing to the special structure of the IEEE 802.11n LDPC parity check matrices, the encoding process can be done very efficiently. The IEEE 802.11n LDPC codes are based on block-structured LDPC codes with circular block matrices [5], i.e. the entire parity check matrix can be partitioned into an array of block matrices; each block matrix is either a zero matrix or a right cyclic shift of an identity matrix. The parity check matrix designed in this way can be conveniently represented by a base (block) matrix. Fig. 1 shows an example base matrix Hb for an IEEE 802.11n LDPC code with code length N¼ 1944 bits and rate¼ 1=2. The block size is Z¼ 81 bits with mb¼ 12 and nb¼ 24. In this matrix, each entry represents a circular right shift of the identity matrix IZ. For example if Z¼ 3 and the entry is 1, then the corresponding block is [0 1 0; 0 0 1; 1 0 0]. The1 entry means a null (all zero) block. In this way the above matrix is a compact expression of a binary 2D [M¼ 12 81, N¼ 24 81] matrix. Note that in the above matrix there are always three non 1 elements at the kbth column (usually they are 1 0 1). This property holds for all 12 LDPC codes defined in IEEE 802.11n [4]. This observation, together with the (dual) diagonal parity check sub-matrix (the right-hand side of Hb), can be explored to encode IEEE 802.11n LDPC codes efficiently. 57 3 30 62 40 0 69 65 64 –1 2 24 –1 –1 –1 53 –1 –1 79 –1 –1 45 56 –1 –1 28 –1 –1 –1 79 –1 –1 –1 –1 61 –1 –1 –1 –1 20 –1 –1 –1 –1 70 57 –1 50 0 24 53 66 8 –1 38 14 0 35 60 –1 –1 37 –1 –1 –1 –1 57 52 –1 –1 –1 11 –1 –1 –1 –1 42 56 –1 –1 –1 –1 –1 –1 –1 –1 3 22 –1 –1 –1 –1 –1 –1 27 50 55 56 35 28 50 52 72 30 77 –1 51 –1 7 14 –1 –1 –1 –1 –1 –1 9 –1 –1 79 –1 –1 –1 –1 –1 –1 27 –1 –1 12 –1 –1 –1 –1 –1 –1 8 –1 –1 32 –1 –1 16 –1 –1 –1 –1 –1 –1 0 –1 –1 –1 –1 1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 –1 0 0 Fig. 1 Example base matrix for N ¼ 1944 bits, rate ¼ 1=2 LDPC code Denote the input kb ¼ nb mb groups of Z bits, i.e. m¼ [m0, m1, . . . , mkb1], where information sequence as m and divide it into each element of m is a vector of length Z. The parity sequence can also be grouped as length of Z bits. Denote the codeword as cb ¼ ½m pŠ ¼ ½m0; m1; . . . ; mkb1; p0; p1; . . . ; pmb1Š Recall that a codeword has to satisfy Hbcb¼ 0, which can be written in a block form as 2 666666664 h0;0; h0;1; . . . ; h0;kb1; h1;0; h1;1; . . . ; h0;kb1; . . . hx;0; hx;1; . . . ; hx;kb1; . . . 2 hmb1;0; hmb1;1; . . . ; hmb1;kb1; 3 3 777777775 1; 0; . . . 1 1; 0; 0 . . . 1 0; . . . 0; 0 . . . 1 1;1; . . . 0  ¼ 0 ð1Þ 77777777777777775 66666666666666664 m0 m1 . .. mkb1 p0 p1 . .. pmb1 The x is the row with second non 1 entry at Expanding the above equation, the following equations hold: the kbth column. P kb1 P j¼0 P P j j j h0;jmj þ P1p0 þ p1 ¼ 0 hi;jmj þ pi þ piþ1 ¼ 0 hx;jmj þ p0 þ px þ pxþ1 ¼ 0 hmb1;jmj þ P1p0 þ pmb1 ¼ 0 ð0th rowÞ i 6¼ 0; x; mb 1 ðxth rowÞ ððmb 1Þth rowÞ ð2Þ ð3Þ where P1p0 makes p0 circular shift 1-cycle. Adding up all the above equations, we have P mb1 i¼0 P kb1 j¼0 p0 ¼ hi;jmj P P kb1 hi,jmj for i¼ 0, . . . , mb 1, j¼0 mb1 li. With p0 in hand, p1 and pmb1 can be easily i¼0 the above equation Define li¼ becomes p0 ¼ obtained from (2): p1 ¼ l0 þ P1p0 pmb1 ¼ lmb1 þ P1p0 ð4Þ ð5Þ P In summary, li¼ Other parity sub-vectors can be solved by upward and downward recursions, according to (2). mb1 li are needed to get the i¼0 codeword c. Since hi,jmj is nothing but a circular shift of mj, the resource requirement is trivial. The algorithm has been verified by software simulation using MATLAB. kb1 hi, jmj and j¼0 P Encoder structure: The method presented above suggests an efficient circuit implementation, which is roughly sketched in Fig.2. The circular shift operation can be done with random access memory (RAM), and the address pointer can be adjusted to get the required operation done in one cycle. The memory requirement is kb  Z bits for message and another mb  Z for l, i.e. the total requirement is the code length N-bit (besides the ROM for Hs). H ROM message Z-bits l i memory for l ¥ Z) bits (mb control kb groups of Z-bit memory/register … + + e g a s s e m parity Fig. 2 Proposed encoder structure for IEEE 802.11n LDPC codes ELECTRONICS LETTERS 7th December 2006 Vol. 42 No. 25 

Conclusions: An efficient encoding algorithm for IEEE 802.11n LDPC codes has been presented. The algorithm is based on the special structure of the parity check matrices of these codes and applicable to IEEE 802.11n LDPC codes and other LDPC codes with similar properties. The design is easy to implement and the memory requirement of the encoding circuit is just the code length. # The Institution of Engineering and Technology 2006 8 October 2006 Electronics Letters online no: 20063126 doi: 10.1049/el:20063126 Z. Cai, J. Hao, P.H. Tan, S. Sun and P.S. Chin (Institute for Infocomm Research, 21 Heng Mui Keng Terrace, Singapore 119613) E-mail: caizh@i2r.a-star.edu.sg References 1 Gallager, R.G.: (MIT Press, Cambridge, MA, USA, 1963). Available at http://justice.mit.edu/ people/gallager.html ‘Low-density parity-check codes’ 2 Richardson, T., and Urbanke, R.: ‘The capacity of low-density parity check codes under message-passing decoding’, IEEE Trans. Inf. Theory, 2001, 47, pp. 599–618 3 IEEE P802.16e=D12: ‘Draft IEEE Standard for Local Metropolitan Area Networks. Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems’, October 2005 4 IEEE P802.11n=D10: ‘Draft IEEE Standard for Local Metropolitan networks—Specific requirements. Part 11: Wireless LAN Medium Access Control (MAC), and Physical Layer (PHY) specifications: Enhancements for Higher Throughput’, March 2006 5 Zhong, H., and Zhang, T.: ‘Block-LDPC: a practical LDPC coding system design approach’, IEEE Trans. Circuits Syst., 2005, 52, (4), pp. 766–775 6 Richardson, T., and Urbanke, R.: ‘Efficient encoding of low-density parity- check codes,’ IEEE Trans. Inf. Theory’, 2001, 47, (2), pp. 638–656 7 Colavolpe, G.: ‘Design and performance of turbo Gallager codes,’, IEEE Trans. Commun., 2004, 52, pp. 1901–1908 8 Flarion, Vector-Low-Density Parity-Check (V-LDPC) Coding Solution http://www.flarion.com/products/ [Online]. Available: Data Sheet ldpc_data_sheet.pdf ELECTRONICS LETTERS 7th December 2006 Vol. 42 No. 25