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:
- Type-I: Minimizing the average symbol cost for a fixed expansion factor (rate).
- 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.
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