Project
`
`IEEE 802.20 Working Group on Mobile Broadband Wireless Access
`
`<http://grouper.ieee.org/groups/802/20/>
`
`Irregular Repeat-Accumulate LDPC Code Proposal – Technology Overview
`2007-03-05 (March 5, 2007)
`
`Thierry Lestable
`Samsung Electronics Research
`Institute, UK
`Joseph Cleveland
`Samsung Telecommunications
`America
`Anna Tee
`Samsung Telecommunications
`America
`IEEE 802.20 Call for Proposals
`
`Email :
`thierry.lestable@samsung.com
`
`Email:
`j.cleveland@samsung.com
`Email:
`atee@sta.samsung.com
`
`This document introduces a new coding scheme based on Irregular Repeat
`Accumulated (IRA) Codes which is proved to be suitable for small packet
`lengths produced by VoIP-like applications, and thus proposed to be
`included into Mobile Broadband Wireless Access Systems as an
`alternative to Convolutional Codes.
`
`For consideration and adoption as a feature for 802.20 standards draft
`This document has been prepared to assist the IEEE 802.20 Working Group. It is offered
`as a basis for discussion and is not binding on the contributing individual(s) or
`organization(s). The material in this document is subject to change in form and content
`after further study. The contributor(s) reserve(s) the right to add, amend or withdraw
`material contained herein.
`The contributor grants a free, irrevocable license to the IEEE to incorporate material
`contained in this contribution, and any modifications thereof, in the creation of an IEEE
`Standards publication; to copyright in the IEEE’s name any IEEE Standards publication
`even though it may include portions of this contribution; and at the IEEE’s sole
`discretion to permit others to reproduce in whole or in part the resulting IEEE Standards
`publication. The contributor also acknowledges and accepts that this contribution may be
`made public by IEEE 802.20.
`The contributor is familiar with IEEE patent policy, as outlined in Section 6.3 of the
`IEEE-SA Standards Board Operations Manual
`<http://standards.ieee.org/guides/opman/sect6.html#6.3> and in Understanding Patent
`Issues During IEEE Standards Development
`<http://standards.ieee.org/board/pat/guide.html>.
`
`Title
`
`Date
`Submitted
`
`Source(s):
`
`
`Re:
`
`Abstract
`
`Purpose
`
`Notice
`
`Release
`
`Patent
`Policy
`
`
`
`
`
`0001
`
`CALTECH - EXHIBIT 2012
`Apple Inc. v. California Institute of Technology
`IPR2017-00701
`
`

`

`I.
`INTRODUCTION
`In the current draft [1] defining the Air Interface of Mobile Broadband Wireless Access
`Systems, two different mandatory coding schemes are used depending on the information
`block length to be transmitted over the air.
`
`Indeed, whilst the rate Rc=1/3 Convolutional Code (CC) is employed for short packets
`whose length is below (or equal) 128 information bits, a rate Rc=1/5 Parallel
`Concatenated Convolutional Code (PCCC) i.e. Turbo code is preferred for higher packet
`length.
`
`We thus propose hereafter an alternative optional coding scheme for encoding short
`packets, by taking advantage of outstanding performances from Irregular Repeat
`Accumulate (IRA) Codes.
`
`Besides offering a linear encoding complexity w.r.t packet length, these codes inherit
`some advantages from both Turbo-Codes, and Low-Density Parity Check (LDPC) Codes.
`They thus induce semi-parallel architectures, resulting in high-throughput decoders,
`together with being decodable by Message-Passing algorithms only, or by Turbo-like
`decoding algorithms.
`
`
`II. BASICS OF IRREGULAR REPEAT ACCUMULATE (IRA) CODES
`Repeat Accumulate (RA) Codes [3], together with their enhanced version Irregular
`Repeat Accumulate (IRA) Codes [4] are part of Sparse Graph Codes family, and as such
`can be seen as a subset of LDPC Codes. On the other hand, we’ll see in the sequel that
`they can also be seen as a concatenated coding scheme. They were introduced first by
`Divsalar et al. in [3], and have drawn initial interest due to their simplicity for theoretical
`studies.
`
`Besides, it can be easily demonstrated that these family of codes offer a linear time
`encoding, which makes them attractive compared with Turbo-Codes or LDPC Codes [15].
`
`The structure of such RA Codes is depicted in Figure II-1 below, where the concatenated
`framework is highlighted:
`
`0002
`
`

`

`
`
`RepeaterRepeater
`
`
`ParallelParallel
`
`To To
`
`SerialSerial
`
`
`
`InterleaverInterleaver
`
`
`SystematicSystematic
`
`OutputOutput
`
`
`
`DD
`
`
`ParityParity
`
`CheckCheck
`
`OutputOutput
`
`Figure II-1 Repeat Accumulate (RA) Code : Concatenated Structure
`
`
`Each of the k information bits forming the packet to be transmitted over the air, are first
`repeated q times. This can be seen as a repetition code of rate 1/q. Those n=kq bits are
`then interleaved and fed into a simple accumulator. This accumulator can be described as
`a rate-1 convolutional code, with a generator polynomial 1/(1+D).
`
`As such, a RA code is the Serial concatenation of two different coders: repetition code,
`and convolutional code.
`
`
`
`Next parity bit is a Next parity bit is a
`
`modulo 2 sum of ALL modulo 2 sum of ALL
`
`previous permuted bitsprevious permuted bits
`
`
`
`Figure II-2 Tanner Graph of RA Codes
`
`
`Moreover, such codes as subset of LDPC Codes can also be easily represented by means
`of their Tanner Graph, cf. Figure II-2: a bipartite graph with bit and parity nodes. This
`means their decoding can be realized by means of any Message-Passing algorithms, and
`offer advantageous inherited parallel architecture.
`
`
`
`0003
`
`

`

`III.
`INTERLEAVER DESIGN
`As outlined in the concatenated structure, the interleaving is a key process whilst
`designing such IRA codes, together with the distribution of the repetitions.
`We are thus going to propose in the sequel two different kinds of interleavers, and
`evaluate their suitability to the encoding of short packets.
`
`
`A. Pseudo-Random Interleaver (Algorithm A)
`We reuse here the ‘S-Random’ algorithm [6], by adapting the ‘S’ factor w.r.t. the
`repetition factor of each variable node (Irregular Code).
`( ) ∑ ⋅
`S
`y
`iy
`Let’s define the following polynomial:
`σ
`=
`σ
`i
`i
`iσ means a fraction of indices, such that, for any two indices m, n from this
`where
`fraction, the following condition is fulfilled:
`
`.
`
`nm
`S
`Π⇒<−
`i
`
`(
`m
`
`)
`
`( )
`n
`≥Π−
`
`S
`
`i
`
`
`
`where Π(m), Π(n) are the resulting indices after permutation.
`
`Note that some i S could be more than N / 2 but all i S must be more than i . A
`disadvantage of the approach is that the interleaver requires memory to store numbers and
`it is not possible to design it on fly.
`
`B. Algebraic Interleaver with induced Randomness (Algorithm B)
`We propose here to use an Algebraic Interleaver which can be generated on the fly, and
`can be fully defined by only few parameters. We particularly focus here on the circular
`shifting interleaver even though many other techniques can be found in [8].
`
`
`IV. SIMULATION RESULTS
`In order to illustrate our results, we’ve decided to evaluate the two proposed schemes,
`namely IRA-A (Pseudo-Random), and IRA-B (Algebraic) codes, for the particular
`transmission of short packets generated by an EVRC vocoder. This is an opportunity
`indeed to draw attention on VoIP-like applications. Such vocoder will produce 3 different
`kinds of information block length, respectively 172, 80 and 16 bits (cf. [9]).
`
`As a result, our evaluation will be compared with a Convolutional Code, since this is
`mainly the coding scheme in use for such lengths.
`
`0004
`
`

`

`With a target FER of 1%, the Algorithm A (IRA-A) ends up with 0.8dB improvement
`compared with the convolutional code (cf. below Figure IV-1).
`
`0
`
`0.5
`
`1
`
`1.5
`
`2
`
`100
`
`10-1
`
`10-2
`
`10-3
`
`10-4
`
`10-5
`
`Pe
`
`Vit-fer
`Vit-ber
`IRA-A-fer
`IRA-A-ber
`
`~0.8 dB
`
`2.5
`
`3
`
`3.5
`
`
`
`Eb/N0
`Figure IV-1 Algorithm A, BER/FER Vs Eb/N0: Full Rate EVRC (172 bits)
`
`
`Now, for the same information length, 172 bits, the second code IRA-B results in 0.5dB
`gain w.r.t. the convolutional case (Figure IV-2).
`
`
`Vit-fer
`Vit-ber
`IRA-B-fer
`IRA-B-ber
`IRA-B-un
`detected-ber
`
`0.5
`
`1
`
`1.5
`
`2
`
`Eb/N0
`
`2.5
`
`3
`
`3.5
`
`
`
`100
`
`10-1
`
`10-2
`
`10-3
`
`10-4
`
`10-5
`
`0
`
`Pe
`
`Figure IV-2 Algorithm B, BER/FER Vs Eb/N0: Full Rate EVRC (172 bits)
`
`
`
`0005
`
`

`

`It is then interesting to evaluate if this gain is maintained whilst decreasing the packet
`length, since it is well known, this is a challenging field for Iterative coding schemes such
`as Sparse graph codes (LDPC Codes).
`
`In the Figure IV-3 (80 bits) and Figure IV-4 (16 bits) below, the IRA-B code still
`outperforms the convolutional code by respectively 0.5dB and 0.7dB.
`
`IRA-B-ber
`Vit-fer
`Vit-ber
`IRA-B-fer
`Vit-BER
`IRA-B-BER
`
`100
`
`10-1
`
`10-2
`
`10-3
`
`10-4
`
`Pe
`
`10-5
`
`0
`
`0.5
`
`1
`
`1.5
`Eb/N0
`
`2
`
`2.5
`
`3
`
`
`
`Figure IV-3 Algorithm B, BER/FER Vs Eb/N0: Rc=1/2 EVRC (80 bits)
`
`
`
`0006
`
`

`

`IRA-B-ber
`Vit-fer
`Vit-ber
`IRA-B-fer
`Vit-BER
`IRA-B-BER
`
`100
`
`10-1
`
`10-2
`
`10-3
`
`10-4
`
`Pe
`
`10-5
`
`0
`
`1
`
`2
`
`3
`Eb/N0
`
`4
`
`5
`
`6
`
`
`
`Figure IV-4 Algorithm B, BER/FER Vs Eb/N0: Rc=1/8 EVRC (16 bits).
`
`
`
`V. CONCLUSIONS
`In this proposal, Irregular Repeat Accumulate (IRA) codes have been demonstrated to be
`suitable candidate technology whilst transmitting short packet length (between 16 and
`172 bits). Besides, their performance outperforms current Convolutional codes by 0.5dB
`to 1dB.
`
`Since these codes offer a linear time encoding, together with parallel decoder architecture
`resulting in very high throughput decoders, it could make sense then to consider them as
`an optional alternative for short packet lengths (<128 bits).
`
`References
`
`[1] ‘Draft Standard for Local and Metropolitan Area Networks - Standard Air Interface for
`Mobile Broadband Wireless Access Systems Supporting Vehicular Mobility - Physical and
`Media Access Control Layer Specification’, IEEE P802.20/D2.1, May 2006.
`[2] 3GPP2 C.S0014-A, “Enhanced Variable Rate Codec, Speech Service Option 3 for Wideband
`Spread Spectrum Digital Systems”, April 2004
`[3] D. Divsalar, H. Jin, and R. J. McEliece, "Coding theorems for turbo-like codes," in 36th
`Allerton Conference on Communications, Control, and Computing, Sept. 1998, pp. 201--210.
`
`0007
`
`

`

`[4] H. Jin, A. Khandekar and R. J. McEliece, “Irregular repeat-accumulate codes," Proceedings
`of the Second International Symposium on Turbo Codes and Related Topics, pp. 18, Brest,
`France, September 2000
`[5] G.D. Forney, Jr., "Codes on graphs: normal realizations," IEEE Transactions on Inform.
`Theory, vol. 47, no. 2, pp. 520 548, Feb 2001
`[6] Tanner R.M. A Recursive Approach to Low Complexity Codes / R.M. Tanner // IEEE
`Transaction on Information Theory. – 1981. –Vol. IT-27, № 9. – P.533-547.
`[7] MacKay D. Information theory, inference and learning algorithms, Cambridge University
`Press, New York, NY, 2002. 550 pp
`[8] S. Dolinar and D. Divsalar “Weight Distribution for turbo codes using random and non-
`random permutation” JPL Progress report 42-122 pp 56-65, Aug 15,1995
`[9] 3GPP2 C.S0002-D, “Physical Layer Standard for cdma2000 Spread Spectrum Systems”,
`Revision D, February 13, 2004
`[10]
`iLBC Internet Low Bitrate Vocoder, <http://www.vocal.com/ilbc.html>
`[11]
`D. Chase, "Code-combining - a maximum likelihood decoding approach for combining
`an arbitrary number of noisy packets," IEEE Trans. on Commun., vol. 33, May 1985.
`[12]
`3GPP2 C.S0047-0 Link-Layer Assisted Service Options for Voice-over-IP: Header
`Removal (SO60) and Robust Header Compression (SO61)
`[13]
`RFC 3095 - RObust Header Compression (ROHC): Framework and four profiles: RTP,
`UDP, ESP, and uncompressed, The Internet Society (2001).
`[14]
`H. D. Pfister, I. Sason and R. Urbanke, "Capacity-achieving ensembles for the binary
`erasure channel with bounded complexity," IEEE Trans. on Information Theory, vol. 51, no.
`7, pp. 2352-2379, July 2005.
`[15]
`T. Lestable, M. Ran et al., “Error Control Coding Options for Next Generation Wireless
`Systems”, White paper from WWRF#17, Heidelberg, Germany, Nov. 2006.
`
`
`
`
`0008
`
`