Source-linked AI summary
Nested Polar Codes for Wiretap and Relay Channels
Mattias Andersson, Vishwambhar Rathi, Ragnar Thobaben, Joerg Kliewer, Mikael Skoglund
TL;DR
The paper addresses capacity and secrecy for degraded wiretap channels and capacity for physically degraded receiver-orthogonal relay channels. It constructs nested polar codes using polarized-channel ordering and proves the resulting schemes achieve the wiretap capacity-equivocation region and relay-channel capacity, with simulations at block length 1024 showing curves close to the secrecy upper bound.
Problem
The paper studies whether polar codes can achieve the full capacity-equivocation region for degraded wiretap channels and capacity for physically degraded receiver-orthogonal relay channels.
Method
The paper constructs nested polar codes by partitioning a polar code into cosets and uses degraded polarized-channel ordering for wiretap and relay coding schemes.
Results
Theorem II.1 establishes the wiretap capacity-equivocation region, while Theorem III.1 gives relay codes of any rate R < C with destination error probability below ε for sufficiently large block parameters.
Takeaways & Limitations
Nested polar codes provide asymptotically capacity-achieving schemes for both the degraded wiretap channel and the physically degraded receiver-orthogonal relay channel.
Abstract
from arXiv · showhide
We show that polar codes asymptotically achieve the whole capacity-equivocation region for the wiretap channel when the wiretapper's channel is degraded with respect to the main channel, and the weak secrecy notion is used. Our coding scheme also achieves the capacity of the physically degraded receiver-orthogonal relay channel. We show simulation results for moderate block length for the binary erasure wiretap channel, comparing polar codes and two edge type LDPC codes.
I. INTRODUCTION
Polar codes transform a binary-input channel into polarized bit-channels and, with suitable information sets, approach symmetric capacity under successive-cancellation decoding. The paper uses degradation ordering to show nested polar codes achieve the degraded wiretap and physically degraded relay-channel capacities.
- Polarization: Polar codes use a length-N transform G = RF ⊗n to create bit-channels that polarize toward error-free or completely noisy behavior.The transform is applied to N bits and transmitted through independent copies of a binary-input memoryless channel.
- Polar codes: The polar code P(N, A) freezes bits outside A, uses the corresponding rows of G, and has rate |A|/N.The frozen set is AC, while the unfrozen indices A determine the codeword.
- Capacity achievement: For β < 1/2, choosing A from bit-channels with Z(i) < 2^-N^β makes the rate approach I(W) as N grows.Under successive-cancellation decoding, the block error probability has an asymptotic upper bound based on the selected bit-channels.
- Nested construction: Nested polar codes partition P(N, A) into cosets of P(N, B), with uA\B selecting the coset and uB carrying the inner-code contribution.Frozen bits are set to zero or matched to corresponding bits in uA\B.
- Applications: For degraded symmetric channels, polarized subchannels preserve degradation ordering, enabling nested polar codes to achieve degraded wiretap and physically degraded relay-channel capacity.The paper identifies these applications in Sections II and III and presents the relay-channel treatment as, to the authors’ knowledge, the first of its kind for a degraded relay channel.
II. NESTED POLAR WIRETAP CODES
The paper constructs nested polar codes for a symmetric wiretap channel with a stochastically degraded wiretapper, achieving the full rate-equivocation region asymptotically. The scheme uses randomized coset selection and establishes both reliable decoding for Bob and sufficient equivocation for Eve.
- Channel model: The wiretap model has binary inputs, symmetric main and wiretapper channels, and a wiretapper channel stochastically degraded with respect to the main channel.A rate-equivocation pair is achievable when the message rate, decoding error, and equivocation satisfy the stated asymptotic conditions.
- Main result: Theorem II.1 states that nested polar codes of length N = 2^n achieve every admissible rate-equivocation pair for sufficiently large n.The main and wiretapper capacities are represented by CM = I(W) and CW = I(˜W) under channel symmetry.
- Code construction: The construction selects nested sets AN and BN, forms subcodes as cosets, and uses a uniformly random vector TN to choose a codeword within the message subcode.The resulting coding rate approaches R because |AN\BN|/N approaches CM − (CM − R).
- Reliability and rate: Bob’s block error probability tends to zero, while the coding rate converges to the target message rate R.The rate calculation uses lim inf_n→∞ |AN|/N = CM.
- Secrecy analysis: For R ≥ CM − CW, the construction yields equivocation at least CM − CW − ε, which is at least Re − ε for sufficiently large n.The analysis uses the Markov relation SN → XN → ZN and bounds H(XN|ZN, SN) through decoding and Fano’s inequality.
- Secrecy analysis: For R < CM − CW, splitting BN into B1N and B2N makes the relevant code decodable given T2N, while the remaining uncertainty supports equivocation approaching R.The resulting bound is H(SN|ZN)/N ≥ R − ε for sufficiently large n.
III. NESTED POLAR RELAY CHANNEL CODES
The paper constructs nested polar codes for the physically degraded receiver-orthogonal relay channel and proves that they achieve capacity asymptotically. The scheme uses block-Markov transmission and handles both capacity-order cases.
- Channel model: The physically degraded receiver-orthogonal relay channel has orthogonal receiver components and symmetric source-relay, source-destination, and relay-destination channels.Its symmetric capacity is C = min {CSD + CRD, CSR}.
- Capacity result: For R < C, a nested polar code of rate R and length (B + 1)2^n achieves destination error probability below any ϵ when B and n are sufficiently large.This is the main asymptotic capacity result for the relay channel.
- Coding scheme: The relay construction uses block-Markov coding with B source codewords transmitted over B + 1 blocks.This organizes relay forwarding across consecutive blocks.
- Coding scheme: When CSR ≤ CSD + CRD, the source transmits nested polar codewords while the relay decodes AN and forwards bits in AN \ BN in the next block.The relay decoding error can be made smaller than ϵ/(3B) by choosing n sufficiently large.
- Coding scheme: When CSR > CSD + CRD, BN is selected from the relay-channel polarized set and AN is chosen as a subset of size N(CSD + CRD) containing BN.The resulting coding rate approaches CSD + CRD as n and B grow.
IV. SIMULATIONS
The simulations evaluate Eve’s equivocation for nested polar and edge type LDPC wiretap codes over binary erasure channels. At block length 1024, the reported curves are close to the equivocation upper bound.
- Simulation setup: The simulations compare nested polar wiretap codes with two edge type LDPC codes on a binary erasure wiretap channel.The main and wiretapper channels have erasure probabilities em and ew, and LDPC curves are ensemble averages.
- Equivocation calculation: For the binary erasure channel, Eve’s equivocation is calculated using parity-check matrices for the overall code and nested subcode.The relevant calculation uses the columns corresponding to erased codeword positions.
- Equivocation calculation: The equivocation calculation is derived from the conditional entropy of the transmitted codeword given the message and Eve’s observation.The proof counts equally likely solutions to the parity-check constraints induced by erased positions.
- Simulation setup: Figure 1 plots Eve’s equivocation rate and the upper bound for Re as a function of ew with R = 0.25 and em = 0.25.The codes use block length N = 1024.
- Results: At block length N = 1024, the equivocation curves are close to the upper bound.This is the paper’s reported moderate-block-length simulation outcome.