PaperlayerView exact revision on arXiv

Source-linked AI summary

Polar Coded Repetition for Low-Capacity Channels

Fariba Abbasi, Hessam Mahdavifar, Emanuele Viterbo

arXiv:2010.16144v1cs.ITmath.IT

TL;DR

Low-power IoT devices may need ultra-low-rate codes, while repetition concatenation can lose achievable rate. The paper modifies polar codewords across repetition blocks and reports higher asymptotic achievable rate than simple repetition over the BEC, with almost unchanged complexity.

  • Problem

    Low-power IoT devices need reliable ultra-low-rate communication, but repetition of moderate-rate codes can incur rate loss.

    Source: §I · p. 1

  • Method

    Polar coded repetition changes selected polarization recursions in each block to transmit slightly modified outer polar-code codewords.

    Source: §I · p. 1, §II · p. 2

  • Results

    Over the BEC, the proposed scheme outperforms simple repetition in asymptotic achievable rate while keeping decoding complexity almost the same.

    Source: §IV · p. 6

  • Takeaways & Limitations

    The scheme offers a higher asymptotic achievable rate than straightforward repetition while retaining nearly the same encoding and decoding complexity.

    Source: §I · p. 1

    The achievable-rate analysis and reported comparison are for the binary erasure channel.

    Source: §IV · p. 6

Abstract

from arXiv · show

Constructing efficient low-rate error-correcting codes with low-complexity encoding and decoding have become increasingly important for applications involving ultra-low-power devices such as Internet-of-Things (IoT) networks. To this end, schemes based on concatenating the state-of-the-art codes at moderate rates with repetition codes have emerged as practical solutions deployed in various standards. In this paper, we propose a novel mechanism for concatenating outer polar codes with inner repetition codes which we refer to as polar coded repetition. More specifically, we propose to transmit a slightly modified polar codeword by deviating from Arikan's standard 2 x 2 Kernel in a certain number of polarization recursions at each repetition block. We show how this modification can improve the asymptotic achievable rate of the polar-repetition scheme, while ensuring that the overall encoding and decoding complexity is kept almost the same. The achievable rate is analyzed for the binary erasure channels (BEC).

I. INTRODUCTION

The paper proposes polar coded repetition to improve the asymptotic achievable rate of repetition concatenation while keeping encoding and decoding complexity almost unchanged. The motivation is the need for reliable, very-low-rate communication under IoT devices’ power and hardware constraints.

I. INTRODUCTION

  • IoT devices’ power and transceiver constraints can require ultra-low-rate codes at very low SNR, where repetition of moderate-rate codes incurs rate loss and mediocre performance.The cited example maps −13 dB SNR to a capacity of 0.03 bits per transmission; the 3GPP approach combines rate-1/3 turbo or convolutional codes with up to 2048 repetitions.Source: §I · p. 1
  • Prior work characterized repetition counts with negligible rate loss for low-capacity channels and studied high-rate polar codes concatenated with repetition for binary symmetric channels [1].The passage also notes that polar codes naturally invoke the characterized repetition count when constructed for low-capacity channels [1].Source: §I · p. 1
  • Over the BEC, polar coded repetition outperforms straightforward polar-repetition in asymptotic achievable rate for any given number of repetitions, with almost the same encoding and decoding complexity.The scheme sends a slightly modified polar codeword in each repetition block by changing selected polarization recursions.Source: §I · p. 1

A. Background

Polar coding recursively transforms a channel into synthetic channels of differing reliability, from which information bits are selected for transmission. Repetition concatenation applies an outer code to the repetition channel, reducing decoding complexity at the cost of asymptotic achievable rate.

A. Background

  • Successive cancellation decodes the first bit using both channel observations, then decodes the second using those observations and the first decoded bit; the resulting synthetic channels have differing reliability.For the BEC, the Bhattacharyya parameter equals the erasure probability.Source: A. Background · pp. 1–2
  • Recursive application of the polar transform yields synthetic channels that become nearly noiseless or noisy, and the encoder places information bits in the best channels while freezing the others.The polar code length is n = 2^m, and its generator is formed from selected rows of the recursively constructed matrix.Source: A. Background · p. 2
  • Repetition concatenation designs an outer code of length n = N/r for the r-repetition channel, then repeats each code bit r times to produce a length-N code.For a BEC(ε), the repetition channel is BEC(ε^r).Source: A. Background · p. 2
  • The repetition concatenation reduces decoding complexity essentially to that of the outer code, but sacrifices asymptotic achievable rate, especially with many repetitions.Source: A. Background · p. 2

II. PROPOSED SCHEME

The proposed scheme modifies selected polarization recursions separately in each repetition block while sharing the remaining transform. This design aims to improve low-rate performance with almost the same computational complexity as straightforward repetition.

II. PROPOSED SCHEME

  • The scheme uses a different r′ × r′ binary matrix in each repetition block while keeping the remaining G^(⊗(m−t′)) transform the same.It modifies the first t′ polarization recursions in each repetition and leaves the remaining m−t′ recursions unchanged.Source: §II · p. 2
  • Choosing r′ = r keeps complexity comparable to straightforward polar-repetition; choosing r′ = n can achieve the channel capacity C(W).Source: §II · p. 2
  • The section illustrates the approach with two and four repetitions, using regular and irregular polar coding, before generalizing the regular scheme to arbitrary repetition r.Source: §II · p. 2

A. Examples for two and four repetitions

The examples vary the polar-code patterns transmitted across repetition blocks to improve capacity while keeping complexity comparable to simple repetition. For BECs, the reported modified schemes outperform repetition baselines, and irregular four-repetition patterns outperform regular ones.

Examples for two repetitions

Example 2 (Four repetitions with regular polar codes)

  • Among the tested regular four-repetition patterns, (P^(0)_4R, P^(3)_4R, P^(3)_4R, P^(3)_4R) has the largest capacity.The search considers 35 multisets of four patterns from the four regular-pattern options.Source: A. Examples for two and four repetitions · p. 3
  • For four repetitions, the modified regular scheme transmits a changed combination in the first block and unmodified codewords in the other three, exceeding repetition capacity on BECs.The codewords are designed for the effective channels observed by their respective length-n/4 sub-blocks.Source: A. Examples for two and four repetitions · p. 3

Example 3 (Four repetitions with irregular polar codes)

  • For BECs, irregular four-repetition patterns have greater capacity than regular patterns, and the modified four-repetition scheme exceeds repetition capacity.The regular-pattern capacity is C4R; the irregular-pattern capacity C4I satisfies C4I > C4R.Source: A. Examples for two and four repetitions · p. 3
  • The irregular four-repetition scheme searches 330 pattern multisets and selects (P^(4)_4I, P^(5)_4I, P^(7)_4I, P^(7)_4I) as the capacity-maximizing combination.Its codewords use distinct effective channels and the resulting capacity exceeds that of the regular-pattern scheme.Source: A. Examples for two and four repetitions · p. 3

B. General case for regular polar codes

For any number of repetitions and any BEC erasure probability strictly between 0 and 1, the regular polar coded repetition scheme has higher capacity than straightforward repetition. The construction uses recursive regular polar patterns, and the proof compares the resulting capacity expression with the repetition benchmark.

B. General case for regular polar codes

  • For r = 2^t repetitions, the regular construction considers r possible t-fold Kronecker products and uses P(0)_2^⊗t for the remaining r − 1 patterns.The section defines ZP(i)_r as the erasure probabilities of the channels observed by the codewords for pattern P(i)_r.Source: B. General case for regular polar codes · pp. 3–4
  • For any r and 0 < ε < 1, the proposed scheme's capacity CrR exceeds the repetition capacity C(W^r).The argument compares the two expressions after showing their difference has no root in (0, 1).Source: B. General case for regular polar codes · pp. 4–5
  • Sturm's algorithm [7] shows the comparison expression has no root for ε in (0, 1); comparing both sides at an interior ε shows the modified scheme has greater capacity than repetition for r repetitions.Source: B. General case for regular polar codes · p. 5

III. ANALYSIS AND NUMERICAL RESULTS

The analysis section introduces numerical comparison of the proposed and straightforward polar-repetition schemes, followed by complexity analysis. It also notes a limitation of Sturm's algorithm for higher-degree polynomials and points to a more efficient alternative.

III. ANALYSIS AND NUMERICAL RESULTS

  • The analysis compares numerical performance of the proposed scheme with straightforward polar repetition, then examines their computational complexity.The passage states the scope of the analyses without reporting their results.Source: §III · p. 5
  • Sturm's theorem completely counts real roots of polynomials, but its implementation becomes inefficient as polynomial degree increases.The footnote identifies this as a practical efficiency limitation.Source: §III · p. 5
  • For higher-degree polynomials, the algorithm proposed in is described as more efficient than Sturm's algorithm.Source: §III · p. 5

A. Numerical Analysis

On the BEC, the proposed polar coded repetition schemes outperform simple repetition for 2, 4, and 8 repetitions. The irregular scheme slightly outperforms the regular scheme at four repetitions, while the gap to the Shannon bound grows as repetitions increase.

A. Numerical Analysis

B. Complexity Analysis

The proposed decoding process adds kernel operations to the outer polar-code and repetition stages. For constant r, its total complexity remains O(n log n).

B. Complexity Analysis

  • The straightforward scheme's total decoding complexity is O(nr + n log n), combining the outer polar code and repetition code costs.Source: B. Complexity Analysis · p. 5
  • The proposed scheme's decoding complexity comprises r kernels, repetition, and a final kernel, with total O(nr + rn log r + n log n/r).Source: B. Complexity Analysis · p. 5
  • For constant r, polar coded repetition has total decoding complexity O(n log n).The stated general expression is O(nr + n log n + n(r−1) log r).Source: B. Complexity Analysis · p. 5

IV. CONCLUSION

Using polar codes as the outer code, the paper transmits slightly modified codewords across repetitions; over BEC, this improves asymptotic achievable rate over simple repetition while keeping decoding complexity almost the same.

IV. CONCLUSION

  • The scheme uses polar codes as the outer code and transmits a slightly modified codeword in each repetition.Source: §IV · p. 5
  • Over BEC, the proposed scheme outperforms simple repetition in asymptotic achievable rate.Source: §IV · p. 6
  • The proposed scheme keeps decoding complexity almost the same as the repetition scheme.Source: §IV · p. 6
Loading 2010.16144v1…