Rate-Constrained Shaping Codes for Structured Sources

Yi Liu, Pengfei Huang, Alexander W. Bergman, Paul H. Siegel

Abstract Shaping codes are essential for encoding information on channels with cost constraints, such as power-limited wireless transmission or wear-constrained flash memory storage. While traditional shaping research often assumes uniform input data, real-world sources are typically structured and non-uniform. This paper establishes a rigorous information-theoretic framework for rate-constrained fixed-to-variable length shaping codes for general i.i.d. sources. By leveraging the theory of word-valued sources, we prove a separation theorem: optimal shaping for structured data can be achieved by concatenating optimal compression with optimal shaping for a uniform source. Furthermore, we introduce the Generalized Expansion Factor (GEF) to characterize optimal distribution matching (DM) codes, providing a unified perspective on shaping and informational divergence.

Introduction

In modern communication and storage systems, different symbols often carry different physical "costs." For instance, in NAND flash memory, high voltage levels cause more physical wear on memory cells than lower levels. Shaping codes are designed to map information into symbol sequences that minimize these costs. However, system requirements frequently impose a strict rate constraint—limiting how much the data can expand during encoding.

Most existing literature focuses on shaping for uniform i.i.d. sources. This paper addresses the practical reality of structured data (e.g., text or database files) and investigates how to design optimal codes that simultaneously account for source structure, channel cost constraints, and target code rates.

Theoretical Framework: Shaping Structured Sources

The authors categorize shaping problems into two primary types based on the optimization objective:

  1. Type-I: Minimizing the average symbol cost for a fixed expansion factor (rate).
  2. Type-II: Minimizing the total cost per source symbol, which accounts for both the symbol cost and the rate overhead.

Using the theory of word-valued sources and Lagrange multipliers, the researchers established the relationship between the code expansion factor and the minimum average symbol cost. A key finding is the existence of an optimal expansion factor that minimizes the total cost per source symbol.

Total Cost vs. Expansion Factor. The curve illustrates the trade-off between rate expansion and cost reduction, identifying an optimal expansion factor that minimizes the average cost per source symbol.

As shown in the figure above, the total cost initially decreases as the expansion factor increases from 1.0, as the encoder gains more freedom to select low-cost symbols. However, beyond a certain point, the overhead of transmitting more symbols outweighs the per-symbol cost savings, leading to an increase in total cost.

The Separation Theorem

A major contribution of this work is the proof of a "separation theorem" for data shaping. Analogous to the source-channel separation theorem, the authors demonstrate that a joint coding scheme is not necessary for optimality. Instead, one can achieve the theoretical limit by first applying an optimal lossless compressor (to "whiten" the structured data) and then applying an optimal shaping code designed for a uniform i.i.d. source. This simplifies system design, allowing engineers to use standard compression algorithms (like LZ77) in tandem with universal shaping modules.

Distribution Matching and the GEF

The paper further explores the duality between shaping codes and Distribution Matching (DM). Optimal shaping is shown to be equivalent to matching a target distribution where a symbol's cost is proportional to its self-information. To evaluate these codes, the authors propose the Generalized Expansion Factor (GEF). This new metric relates shaping performance directly to informational divergence (KL-divergence).

Practical implementation was demonstrated using Varn codes, a tree-based variable-length coding technique. The results showed that Varn codes are asymptotically optimal distribution matchers, with their GEF approaching the theoretical lower bound as codebook size increases.

Experimental Results and Impact

The proposed framework was validated using real-world datasets, including English text (The Count of Monte Cristo) and Chinese text (Collected Works of Lu Xun).

In applications to Multi-Level Cell (MLC) NAND flash memory, the "Compression + Varn coding" scheme significantly outperformed simple compression or direct shaping. By reducing the average voltage levels applied to the cells, the shaping codes effectively lowered the Bit Error Rate (BER) over thousands of Program/Erase (P/E) cycles, directly extending the physical lifespan of the hardware. These results highlight that shaping provides a reliability gain that is distinct from and additive to the gains provided by standard data compression.

Conclusion

This research provides a unified theoretical foundation for rate-constrained shaping of structured sources. By proving the optimality of a separated compression-shaping architecture and introducing the GEF metric, the authors offer both a theoretical roadmap and practical tools (like Varn-based DM) for improving the efficiency and longevity of cost-constrained communication and storage systems.

Summary updated

Abstract

Shaping codes are used to encode information for use on channels with cost constraints. Applications include data transmission with a power constraint and, more recently, data storage on flash memories with a constraint on memory cell wear. In the latter application, system requirements often impose a rate constraint. In this paper, we study rate-constrained fixed-to-variable length shaping codes for noiseless, memoryless costly channels and general i.i.d. sources. The analysis relies on the theory of word-valued sources. We establish a relationship between the code expansion factor and minimum average symbol cost. We then determine the expansion factor that minimizes the average cost per source symbol (total cost), corresponding to a conventional optimal source code with cost. An equivalence is established between codes minimizing average symbol cost and codes minimizing total cost, and a separation theorem is proved, showing that optimal shaping can be achieved by a concatenation of optimal compression and optimal shaping for a uniform i.i.d. source. Shaping codes often incorporate, either explicitly or implicitly, some form of non-equiprobable signaling. We use our results to further explore the connections between shaping codes and codes that map a sequence of i.i.d. source symbols into an output sequence of symbols that are approximately independent and distributed according to a specified target distribution, such as distribution matching (DM) codes. Optimal DM codes are characterized in terms of a new performance measure - generalized expansion factor (GEF) - motivated by the costly channel perspective. The GEF is used to study DM codes that minimize informational divergence and normalized informational divergence.
BibTeX
@article{liu2020rate,
  author = {Yi Liu and Pengfei Huang and Alexander W. Bergman and Paul H. Siegel},
  title = {{Rate-Constrained Shaping Codes for Structured Sources}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  url = {https://openreview.net/forum?id=v1gLvOxjQP2},
}
Figure