PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Polar Codes for Source Coding

Bashar Huleihel, Ziv Aharoni, Haim H. Permuter

arXiv:2610.13554v1cs.IT

TL;DR

For unknown or dependent non-binary sources, exact model-based polar decoding can be computationally impractical. The paper replaces analytical SC operations with neural polar decoders trained from data and uses them in lossless, lossy, and Wyner–Ziv coding. The learned constructions closely match analytical benchmarks when available and remain applicable when source models or analytical decoding rules are unavailable.

  • Problem

    For non-binary sources with memory, analytical SC/SCT decoding requires an explicit source model and can be computationally prohibitive.

    Source: §III · p. 5

  • Method

    Neural polar decoders replace analytical SC updates with learned polarized distributions, supporting lossless, lossy, and Wyner–Ziv polar coding.

    Source: §I · pp. 2–3

  • Results

    Learned constructions closely match analytical benchmarks when available and remain applicable when explicit source models or analytical decoding rules are unavailable.

    Source: §VII · p. 28

  • Takeaways & Limitations

    The framework provides a unified data-driven approach to estimating source-coding limits and constructing lossless, lossy, and Wyner–Ziv codes in difficult modeling or computation regimes.

    Source: §I · p. 3

    The framework focuses on single-encoder, single-decoder problems; multiterminal coding introduces additional challenges, including rate-region objectives and joint decoding.

    Source: §I · p. 2

Abstract

from arXiv · show

This paper presents a data-driven approach to lossless and lossy source compression using polar codes. Classical polar source coding achieves fundamental limits with low complexity for binary memoryless sources. However, for unknown q-ary sources with memory, successive-cancellation (SC) decoding requires an explicit source model and can be computationally prohibitive. We present analytical SC recursions and show that exact implementations scale quadratically with alphabet size and cubically with state-space size. To overcome these limitations, we develop neural polar decoders trained directly from data to approximate conditional distributions of synthetic polar coordinates without requiring an explicit source model. These learned distributions enable estimation of entropy rates, mutual information, and rate-distortion functions, and support explicit polar compression schemes. For lossless compression, we identify high-entropy polarized coordinates and reconstruct the remaining coordinates using the learned SC recursion. For lossy compression, we combine neural polar decoders with a neural test channel to estimate and optimize the mutual information-distortion tradeoff and construct an explicit lossy polar code. We also extend the framework to Wyner-Ziv compression with decoder side information by learning conditional polarized distributions and a reconstruction mapping. Experiments on memoryless sources, sources with memory, and real genomic data show that the learned decoders closely match analytical SC decoders when available and remain applicable when conventional methods are computationally infeasible or the source model is unavailable.

I. INTRODUCTION

Polar source coding reaches compression limits in simple settings, but unknown, dependent, non-binary sources can make exact model-based decoding impractical. This section introduces a data-driven neural–polar framework and its lossless, lossy, and Wyner–Ziv extensions.

I. INTRODUCTION

  • The neural–polar framework replaces analytical SC check-node and bit-node updates with trainable modules, avoiding explicit source models and costly alphabet or state-space enumeration.It targets single-encoder, single-decoder problems, including Wyner–Ziv coding with decoder-only side information.Source: §I · p. 2
  • NPDs estimate polarized conditional distributions for entropy estimation, coordinate selection, and SC reconstruction; on E. coli, arithmetic coding achieved 1.883 bits per base, comparable to NNCP.The learned decoder closely reproduces analytical SC or SCT behavior where those baselines are tractable.Source: §I · p. 2
  • Two NPDs estimate polarized-sequence entropy and conditional entropy to estimate mutual information, while a distortion-penalized score-function update optimizes the neural test channel.The resulting statistics support estimated rate–distortion points and an explicit polar lossy code.Source: §I · pp. 2–3
  • The Wyner–Ziv extension jointly learns a multi-letter auxiliary test channel, reconstruction mapping, and conditional polarized distributions for the conditional mutual-information term.Its rate-carrying coordinates are difficult to infer from side information but predictable from the source through the learned test channel.Source: §I · p. 3

A. Binary Polar Codes for Source Coding

  • Binary polar compression stores the least predictable transformed source bits, whose conditional entropies approach 0 or 1 as block length grows.The polar transform maps a source block to synthetic coordinates; the least predictable set determines the compression rate.Source: A. Binary Polar Codes for Source Coding · p. 4

B. Lossless compression using polar codes

  • Correction information T records SC decoding mismatches, allowing the decoder to correct errors and recover the original sequence exactly.The encoder simulates SC decoding and sends the mismatch indices along with the compressed coordinates.Source: B. Lossless compression using polar… · p. 5

III. POLAR CODING BEYOND BINARY MEMORYLESS SOURCES

  • Analytical non-binary SC and finite-state SCT recursions expose alphabet- and state-space-dependent complexity, motivating data-driven decoders when exact computation is impractical.The section presents the recursions as baselines beyond binary memoryless sources.Source: §III · p. 5

A. Memoryless sources

The paper develops analytical SC recursions for non-binary memoryless and finite-state sources, then replaces their model-dependent operations with neural modules trained from samples. The learned conditional distributions support lossless polar compression without requiring an explicit source model.

A. Memoryless sources

  • Exact non-binary SC decoding requires O(|X|^2 N log N) operations, compared with O(N log N) in the binary case.The non-binary check-node operation computes |X| output metrics, each requiring a sum over |X| symbols.Source: A. Memoryless sources · p. 6

B. Sources with memory

  • For finite-state sources, analytical SCT decoding has complexity O(|S|^3|X|^2 N log N) under the stated time-homogeneous source model.The recursion uses a trellis-based polar construction and sums over intermediate states.Source: B. Sources with memory · pp. 6–7

IV. DATA-DRIVEN LOSSLESS POLAR COMPRESSION

  • NPDs adapt polar SC decoding to finite-alphabet source coding by learning the required posterior quantities directly from samples, without an explicit analytical source model.The framework preserves the polar transform and SC computation graph while replacing analytical update operations with neural modules.Source: §IV · p. 7, A. Neural polar decoder · p. 8

A. Neural polar decoder

  • The NPD minimizes cross-entropy between true and learned polarized conditional distributions, then uses empirical leaf-wise cross-entropies to select unpredictable coordinates.The chosen coordinates form the transmitted set; the learned recursion reconstructs the remaining coordinates.Source: A. Neural polar decoder · pp. 8–9
  • For fixed neural architecture, the NPD recursion has complexity O(kdN log N), with linear dependence on |X| from the softmax head and no |S| dependence.It avoids the analytical recursions’ explicit |X|^2 alphabet and |S|^3 state-space enumerations.Source: A. Neural polar decoder · p. 10

B. Experiments

On the |X|=5 memoryless source, NPD symbol error rates closely follow analytical SC results. For |X|=23, only NPD results are reported because classical SC decoding is computationally infeasible with the implementation used.

B. Experiments

  • The experiments report that NPDs imitate SC and SCT decoders across alphabet sizes and memory orders, including regimes where analytical recursions are prohibitive or source models are unavailable.The section also includes real-world data to which classical SC/SCT algorithms cannot be directly applied.Source: B. Experiments · p. 10

1) Memoryless Sources with Large Alphabet Sizes:

  • NPD symbol error rates closely follow SC decoder results for the |X|=5 memoryless source across different block lengths.The comparison uses probability vector PX = [0.15, 0.15, 0.05, 0.05, 0.6].Source: 1) Memoryless Sources with Large… · p. 10
  • For |X|=23, NPD symbol error rates decrease with increasing block length, while classical SC results are omitted as computationally infeasible.The source has entropy H(X) = 2.0176; the implementation’s explicit |X|^2 alphabet enumeration makes SC infeasible.Source: 1) Memoryless Sources with Large… · pp. 10–11

2) Sources With Memory:

For sources with memory, learned polar decoders track analytical decoding when tractable and approach entropy-rate compression when analytical decoding is impractical. The section also introduces neural test-channel modeling and NPD-based mutual-information estimation for lossy coding.

2) Sources With Memory:

  • For a binary second-order Markov source, NPD performance closely follows the analytical SCT decoder without access to the Markov transition model.The learned decoder captures the trellis-based recursion.Source: 2) Sources With Memory · p. 11
  • For a sixth-order Markov source, NPD compression rates approach the entropy rate as block length increases, without running the computationally impractical SCT decoder.The exact-reconstruction correction scheme applies at every block length.Source: 2) Sources With Memory · p. 11

3) Real-world data:

  • On the E. coli genome, arithmetic coding driven by NPD probabilities achieved 1.883 bpb, comparable to the 1.885 bpb NNCP result, though the evaluation methods differ.The experiment demonstrates applicability to genomic data, not a performance improvement.Source: 3) Real-world data · pp. 11–12, Table I · p. 12

V. LOSSY COMPRESSION VIA NPD

  • For stationary ergodic sources, the operational rate–distortion function is obtained as the block-length limit of a multi-letter optimization.The N-th order objective minimizes mutual information subject to an expected-distortion constraint.Source: §V · p. 12

A. Neural Test Channel:

  • The neural test channel models reconstruction symbols conditioned on the complete source block, allowing temporal dependencies beyond the i.i.d. setting.It is parameterized by an encoder–decoder transformer.Source: A. Neural Test Channel · p. 13

B. Mutual Information Estimation:

  • For a fixed test channel, two NPDs estimate the unconditional entropy of the polarized reconstruction and its conditional entropy given the source; their difference estimates mutual information.The conditional NPD receives the source realization through a source-dependent embedding.Source: B. Mutual Information Estimation · pp. 13–14

C. Distortion-Constrained Mutual Information Optimization

The test-channel parameters are updated to trade off estimated mutual information and distortion, using an NPD-based score-function gradient. Alternating these updates with NPD estimation yields rate–distortion estimates and learned statistics for an explicit lossy polar code.

C. Distortion-Constrained Mutual Information Optimization

  • The test-channel update uses a score-function gradient with an NPD plug-in information-density estimate and a distortion penalty.The sampled discrete reconstruction makes direct differentiation unavailable; the score-function estimator supports Monte Carlo gradient estimation.Source: C. Distortion-Constrained Mutual… · p. 15
  • With NPD parameters fixed, the test-channel gradient estimates the learned-surrogate gradient, but is not necessarily an unbiased estimate for the true objective gradient.If the conditional NPD matches the true conditional distribution at the current test channel, the estimate is unbiased for the true gradient.Source: C. Distortion-Constrained Mutual… · p. 15
  • NPD estimation and test-channel updates alternate; an NPD-only warm-up first provides an initial information-density estimate for the test-channel update.The repeated procedure estimates the rate–distortion tradeoff and learns statistics used to construct an explicit lossy polar code.Source: C. Distortion-Constrained Mutual… · pp. 15–16

Lossy Polar Code Construction:

The lossy polar construction uses learned polarized distributions to encode and decode selected coordinates. Across binary symmetric and first-order Markov sources, estimated rate–distortion curves track analytical or numerical references, while finite-block operating points lie near or above those curves.

Lossy Polar Code Construction:

  • The Honda–Yamamoto construction replaces model-based synthetic distributions with learned NPDs, partitions coordinates into shared, transmitted, and decoder-reconstructed sets, then applies the inverse polar transform.The encoder samples with the conditional NPD; the decoder uses the unconditional NPD for untransmitted coordinates.Source: Lossy Polar Code Construction · pp. 16–18

D. Experiments

  • For binary symmetric and first-order Markov sources, estimated rate–distortion curves track analytical or numerical references; achieved finite-block operating points approach or lie above those curves.For the Markov source, estimated points lie close to and slightly above the numerical Blahut–Arimoto curve, while coding points lie above the estimated curve.Source: Figure 4 · p. 18, D. Experiments · pp. 18–19
  • For E. coli under symbolwise Hamming distortion, the estimated rate near zero distortion closely matches the lossless rate of 1.883 bpb.The plotted comparison uses the rate–distortion function of a uniform memoryless quaternary source as a baseline.Source: Figure 5 · p. 19, D. Experiments · p. 19

VI. WYNER–ZIV VIA NPD

The Wyner–Ziv extension learns conditional polarized distributions, an auxiliary description, and a decoder reconstruction mapping to compress a source when side information is available only at the decoder. Conditional polarization and nested index sets provide the basis for polar coding under stated FAIM assumptions.

A. Problem Formulation

  • The encoder maps the source to an auxiliary description, while the decoder reconstructs from that description and its side information under a distortion constraint.The neural formulation restricts the finite-block optimization to a prescribed auxiliary alphabet and parameterized test-channel and reconstruction families.Source: A. Problem Formulation · p. 20, N inf PUN |XN , gN I(XN; U N|Y N), (47) · p. 20

B. Conditional Polarization and Nested Index Sets

  • For FAIM source pairs satisfying the stated Markov condition, conditional polarization yields nested high-entropy sets whose asymptotic size difference equals the conditional mutual-information rate.The construction applies conditional polarization separately with observations XN and YN.Source: B. Conditional Polarization and Nested… · p. 21
  • The nested polar-coding theorem gives deterministic codes with a rate tied to the transmitted index set and reconstruction meeting the specified distortion bound.The decoder also recovers the encoder-generated auxiliary sequence with probability tending to one.Source: B. Conditional Polarization and Nested… · pp. 21–22

C. Neural Test Channel and Reconstruction Models

  • The neural test channel generates the auxiliary description from the source, and a separate reconstruction mapping forms the decoder output from the description and side information.The reconstruction mapping may process both sequences noncausally across the block.Source: C. Neural Test Channel and… · pp. 22–23

D. Optimization and Estimation Scheme

The Wyner–Ziv procedure alternates neural estimation of conditional mutual information with updates to the auxiliary test channel and reconstruction model. The learned conditional polarized distributions then determine which coordinates are transmitted and decoded using side information.

D. Optimization and Estimation Scheme

  • Two conditional NPDs estimate the rate term as the difference between polarized-sequence entropy conditioned on side information and entropy conditioned on the source.The estimate is a plug-in estimate of normalized conditional mutual information.Source: D. Optimization and Estimation Scheme · pp. 23–24

Optimization Stage:

  • With NPD parameters fixed, the test channel and reconstruction model are updated using a Lagrangian objective with a distortion penalty.The reconstruction parameters affect only the distortion term, and estimation and optimization alternate.Source: Optimization Stage · pp. 24–25
  • The plug-in Monte Carlo gradient estimates the test-channel gradient unbiasedly for the learned surrogate, and is unbiased for the true objective when both conditional NPDs match their true distributions.Repeating the estimation and optimization steps estimates the Wyner–Ziv tradeoff and learns a lossy polar scheme with decoder side information.Source: Optimization Stage · pp. 24–25
  • The Wyner–Ziv polar construction transmits coordinates reliable from the encoder’s source view but uncertain given decoder side information; other low-entropy coordinates are reconstructed using that side information.The transmitted set is A = Fy \ Fx, and the three coordinate sets partition the block.Source: Optimization Stage · pp. 25–26

E. Experiments

Experiments report close tracking of the analytical Wyner–Ziv curve for a binary symmetric source, lower rates with side information for a Markov source, and substantial rate reduction on E. coli. The conclusion also identifies multiterminal source coding as future work.

E. Experiments

  • The binary-source estimates closely track the analytical Wyner–Ziv curve, while Markov-source Wyner–Ziv points have lower rates than the no-side-information benchmark.The binary source uses BSC(0.2) decoder side information; the Markov experiment demonstrates application beyond the memoryless benchmark.Source: E. Experiments · pp. 26–27
  • On the E. coli source, decoder-only side information substantially reduces the rate required at a given Hamming distortion.The comparison includes NPD-estimated pairs with and without side information and corresponding coding operating points.Source: E. Experiments · p. 27, Figure 7 · p. 27

VII. CONCLUSIONS AND FUTURE WORK

  • The paper concludes that learned constructions closely match analytical benchmarks when available and remain applicable when explicit source models or analytical decoding rules are unavailable.The framework combines NPDs with neural test channels for lossy coding and learned conditional polarized distributions and reconstruction for Wyner–Ziv coding.Source: §VII · p. 28
  • Future work includes multiterminal coding such as Slepian–Wolf, requiring coupled synthetic conditional distributions, encoder-specific transmitted sets, and a joint decoder.Each encoder would use only its local observation.Source: §VII · p. 28

APPENDIX A PROOF OF LEMMA 1

The appendices derive probability-domain successive-cancellation recursions and convert them into log-domain updates. The finite-state derivation splits the trellis at its midpoint and sums over the intermediate state.

APPENDIX A PROOF OF LEMMA 1

  • For the memoryless source, the polar-kernel decomposition yields odd- and even-index probability recursions, which are converted into log-domain updates.The proof follows Arıkan’s derivation adapted to source coding over GF(q).Source: Appendix A · pp. 28–29

APPENDIX B PROOF OF LEMMA 2

  • For a finite-state source, the SCT proof splits the trellis at its midpoint, sums over the intermediate state, and marginalizes undecoded symbols to obtain odd- and even-index recursions.Taking logarithms of the probability-domain recursions gives the stated log-domain updates.Source: Appendix B · pp. 30–31
  • The finite-state recursion uses the source’s Markov property and time homogeneity so both length-N segments follow the same transition law.The derivation adapts trellis-based polar constructions to source coding over GF(q).Source: Appendix B · p. 30

APPENDIX C PROOF OF THEOREM 1

The proof separates the mutual-information and distortion gradients, then establishes fast conditional polarization, nested high-entropy sets, and their rate difference for the Wyner–Ziv setting.

APPENDIX C PROOF OF THEOREM 1

  • The score-function identity gives the distortion gradient, while normalization makes the expected derivative of the information density zero.The mutual-information derivative is expressed using information density.Source: Appendix C · pp. 31–32
  • Because the mapping from ˆX^N to U^N is bijective, Iϕ(X^N; ˆX^N) equals Iϕ(X^N; U^N).Source: Appendix C · p. 31

APPENDIX D PROOF OF LEMMA 3

  • Conditional FAIM polarization applied with observations X^N and Y^N yields nested fast high-entropy sets whose asymptotic size difference is I(X; U|Y).The proof uses the block Markov relation to order coordinatewise conditional entropies.Source: Appendix D · pp. 32–33
  • The q-ary extension uses modulo-q operations and normalized conditional entropy to obtain conditional and fast polarization.The high-entropy set densities converge to H(U|Z)/log q for Z=X and Z=Y.Source: Appendix D · pp. 32–33
  • The block Markov relation gives H(Ũ_i|Ũ^{i−1},X^N,Y^N)=H(Ũ_i|Ũ^{i−1},X^N), supporting the coordinatewise ordering and set inclusion.Source: Appendix D · p. 33

APPENDIX E PROOF OF THEOREM 2

The proof constructs a Wyner–Ziv polar code by approximating a target law with a randomized successive encoder, then establishing reliability, rate, distortion, and a deterministic realization.

APPENDIX E PROOF OF THEOREM 2

  • The proof’s five stages establish target-law approximation, SC reliability, asymptotic rate, distortion transfer, and derandomization.The randomized encoder’s induced law approaches the prescribed target law in total variation.Source: Appendix E · p. 33
  • The randomized encoder differs from the target sequential factorization only on frozen coordinates, enabling a total-variation bound.The block Markov relation makes the target conditional law of Ũ^N given (X^N,Y^N) equal to its law given X^N.Source: Appendix E · p. 34
  • The decoder reconstructs Ũ^N successively, using known symbols at frozen and information indices and MAP decisions at the remaining indices.The proof bounds block error by considering the first decoding error and transferring the bound between laws using total variation.Source: Appendix E · pp. 34–35
  • Fast polarization and the conditional-entropy set densities establish the code’s asymptotic rate.The proof transfers fast polarization to normalized entropy sets using a Bhattacharyya-to-entropy comparison.Source: Appendix E · p. 35
  • A selection argument fixes frozen symbols and encoder seeds to obtain a deterministic code while preserving the asymptotic distortion guarantee.The frozen vector is part of the code specification, so fixing the realization does not alter the message set or rate.Source: Appendix E · p. 36

APPENDIX F PROOF OF THEOREM 3

The proof extends the Theorem 1 gradient argument to the Wyner–Ziv objective, accounting for test-channel dependence on the side information.

APPENDIX F PROOF OF THEOREM 3

  • The Wyner–Ziv gradient proof adds the test-channel dependence of the conditional distribution given side information.Source: Appendix F · p. 37
  • Under Theorem 3’s assumptions, strictly positive differentiable softmax test-channel probabilities permit differentiation through the finite sums.Source: Appendix F · p. 37
  • Using Iϕ(X^N;U^N|Y^N) as expected information density, the proof applies the score-function argument and normalization to establish the objective gradient.Source: Appendix F · p. 37

APPENDIX G IMPLEMENTATION DETAILS FOR EXPERIMENTS

The appendix documents recursive NPD loss computation and the architectures, preprocessing, and training and evaluation settings used in the lossless, lossy, and Wyner–Ziv experiments.

A. Recursive Loss Computation

  • The recursive loss procedure evaluates per-block loss along the SC decoding tree and returns updated loss and symbols for the current depth.Check-node and bit-node networks produce child embeddings, and returned symbols are combined through the kernel.Source: A. Recursive Loss Computation · p. 38

B. Lossless Experiments

  • Lossless experiments share the recursive NPD structure, while the E. coli experiment uses larger embedding and hidden dimensions for its richer empirical distribution.The multilayer-module cost remains independent of N and |S|, preserving O(N log N) scaling.Source: B. Lossless Experiments · p. 38

1) DNA Preprocessing and Rate Accounting:

  • E. coli data retain only canonical bases, map them to GF(4), and use a chronological split with 95% for training and 5% for validation.The NPD’s successive probabilities drive arithmetic coding of transformed validation blocks, which are inverted for reconstruction.Source: 1) DNA Preprocessing and Rate Accounting · pp. 38–39
  • The reported 1.883 bpb is the actual arithmetic-coded length per retained validation base, evaluated on data held out from training.The model is trained on the first 95% of the sequence.Source: 1) DNA Preprocessing and Rate Accounting · p. 39

C. Lossy Experiments

  • Lossy experiments train NPDs jointly with a neural test channel, repeating the alternating procedure across Lagrange multipliers to obtain rate–distortion operating points.The same implementation parameters are used for the binary symmetric and first-order Markov sources.Source: C. Lossy Experiments · p. 39, Table III · p. 39

D. Wyner–Ziv Experiments

  • Wyner–Ziv experiments use conditional NPDs, an auxiliary test channel, and a side-information-aware reconstruction network; larger dimensions accommodate Markov-source memory and conditional dependence.The learned components are evaluated at a larger block length with SCL decoding, without retraining the reused modules.Source: D. Wyner–Ziv Experiments · pp. 40–41, Table IV · p. 41
Loading 2610.13554v1…