Kurate.org
Rankings
Back to Rankings

Encoding Trees: A Method for Producing a Variable-Length Prefix Code From Sets of Arbitrary Size

Bryony H. Laporte, Karen Rudie

Oct 21, 2026arXiv:2610.29032v1
cs.IT
Share
Scorecard· 14/16
3.5/10 impact

Correct, tidy formalization of a simple balanced-tree bits<->symbols mapping, but elementary, unbenchmarked, and close to truncated-binary/mixed-radix coding with narrow audience.

Abstract

In this work we formalize a new class of binary trees called encoding trees. We extend this structure in two ways, through labelling to create the class of labelled encoding trees, and pruning to create the class of pruned encoding trees. We discuss how these two extensions can be combined to create the the class of pruned labelled encoding trees. Using the supplementary results that we prove about these classes of trees, we construct a code that uses pruned labelled encoding trees to convert a string of symbols from a sequence of non-empty sets to a binary string. We prove that this code is a variable-length prefix code that can process any valid string of symbols from the given sequence of non-empty sets. Furthermore, we construct a code from the class of pruned labelled encoding trees that goes in the opposite direction, from binary strings to a string of symbols from a sequence of non-empty sets of arbitrary symbols. We prove that this code is also a variable-length prefix code that can process any binary string of any length, provided that the sequence of non-empty sets is sufficiently long. We provide an equation that establishes the minimum sequence length to encode any binary string of a given length, based on that length.

AI Impact Assessments

(1 model)

Core Contribution

The paper defines "encoding trees" Te(x), recursive binary trees that split x leaves into ⌊x/2⌋ and ⌈x/2⌉. It adds ordered labels and a "pruning height" h that removes right subtrees from layer h downward. From these it builds two codes:

  • LtoB: a string of symbols, each drawn from its own set in a sequence of sets, is mapped to a concatenation of root-to-leaf path bits. It is a prefix code and is defined on all inputs.
  • BtoL: an n-bit string is decoded into symbols, one per set in the sequence. At each step the tree for the current set is pruned to the number of remaining bits, and the unique leaf whose path is a prefix of the remaining bits is emitted. The code is defined on all n-bit strings iff Σ⌊log₂|Lᵢ|⌋ ≥ n.

    • The aim is a bijection-like mapping between arbitrary bit strings and symbol strings where the alphabet size varies by position, including sizes that are not powers of two. The motivation is encrypting discrete-event-system behaviour into plausible event sequences for confidentiality.

    The idea is neat. The pruning trick lets the final tree consume exactly the remaining bits, and path bits are skipped where there is no branching. This is a clean, deterministic way to embed bits into variable-size alphabets.

    Methodological Rigor

    The paper is purely theoretical, with inductive proofs for each lemma. The leaf-count, fullness, balancedness, path-length and pruned-leaf-count results are correct, and Proposition 1, the key "b or both b0 and b1" property, is plausible and carefully argued. The proofs are verbose and repetitive, but the claims appear sound.

    Several gaps limit rigor:

  • Theorem 2's "prefix code" argument is loose. Prefix-freeness of the overall BtoL map rests on the sequence of sets being known and on each tree consuming a prefix. Its definition of "variable-length prefix code" also conflates input and output sides.
  • The remark on output length (≥ n / max log₂|Lᵢ|) is imprecise.
  • Almost all the mathematics is elementary: floor and ceiling identities and tree induction.
  • There is no analysis of efficiency or redundancy. The map is not shown to be injective in the sense of mapping distinct bit strings to distinct symbol strings. The sufficient-length condition is shown, but nothing is said about the information-theoretic cost of the "wasted" bits when |Lᵢ| is not a power of two.
  • There are no comparisons with the closest known constructions.

    • Potential Impact

    The impact is likely modest and niche.

  • Closest prior art. The problem is closely related to well-known techniques that are not discussed. These include truncated binary (phase-in) codes, which are exactly the balanced-tree prefix codes for a uniform source over x symbols. They also include arithmetic and range coding used inversely (e.g., distribution-transforming encoders in steganography), mixed-radix conversion, and "bits-to-symbols" mappings in index modulation and DNA storage. The paper's LtoB is essentially truncated binary coding per symbol. BtoL is a bit-to-symbol decoder, similar in spirit to Huffman-based and arithmetic-based steganographic encoding. The novelty is therefore mainly in formalization, not in a new capability. The related-work section compares to Huffman, Fano and Khodak codes, which are compression-focused and less relevant.
  • Applications. Event-based cryptography for discrete-event systems (the authors' niche), format-preserving encoding, steganography, and encoding data into constrained alphabets such as DNA or tokens. The paper gives no demonstrations or experiments.
  • Audience. Probably a small group in discrete-event-systems security and perhaps coding theorists. Wider uptake is unlikely, since the mechanism is simple and practitioners can already do equivalent things with existing tools.

    • Timeliness & Relevance

    The need to map bitstreams onto structured or variable-alphabet symbol streams (steganography, LLM-text watermarking, DNA storage, format-preserving encryption) is real and current. However, the paper does not engage with these communities, so its relevance is largely potential. Venue choice (IEEE Trans. Information Theory) is ambitious for the depth of the results.

    Strengths

  • Clean, self-contained formalism with fully worked examples (e.g., the 8-bit BtoL example).
  • A precise sufficiency-and-necessity condition for coverage (Proposition 3).
  • The pruning construction elegantly handles the final partial symbol.
  • Clear exposition of why a naive fixed prefix mapping fails, via the example showing that the lengths must be within one bit.

    • Limitations

  • The results are elementary, and the heavy proof machinery for simple facts hides the small core insight.
  • It does not discuss the relationship to truncated binary codes, mixed-radix and arithmetic-coding approaches, so the novelty claim is overstated.
  • It offers no efficiency, redundancy or complexity analysis, and no implementation, experiments or application demonstration.
  • The security motivation is not evaluated, so confidentiality implications are untested.
  • Prefix-code and decodability arguments for BtoL are less formal than those for the tree lemmas.
  • The paper is long and repetitive for the contribution. There are also typos and inconsistencies (e.g., sets written as {…} vs ⟨…⟩, "sumk").

    • Overall

    This is a competent but incremental formalization with a useful but modest building block. It is unlikely to be widely cited beyond the authors' own discrete-event-security line of work.

    Rating:3.5/ 10
    Significance 3Rigor 5.5Novelty 3.5Clarity 5.5

    Generated Oct 22, 2026

    Comparison History (0)

    No comparisons yet.