Research on Universal Combinatorial Coding

Jun Lu, Zhuo Zhang, Juan MoThe Scientific World JOURNAL 2014 · DOI

TL;DR

This paper introduces "Universal Combinatorial Coding" (UCC), a novel lossless coding method that bridges existing coding branches (source, channel, secrecy) by leveraging combinatorics. UCC offers a unified framework that is independent of source probability, enabling applications in compression, encryption, and error detection with theoretical efficiency close to the source entropy limit.

What Problem Does This Paper Address?

Traditional coding theory is often siloed into distinct branches: source coding for data compression, channel coding for reliability, and secrecy coding for security. While these methods are effective in their domains, they operate largely independently. This paper posits that there's an underlying universality among these coding methods, suggesting the existence of a unifying principle. The authors aim to bridge this gap by proposing Universal Combinatorial Coding (UCC), a method that draws from combinatorial theory to create a unified approach applicable across these different coding domains. UCC seeks to overcome the limitations of probability-dependent methods by offering a robust, probability-independent framework.

Methods

The core of UCC lies in its combinatorial approach to assigning a unique ordinal (positional) number to any given sequence. This is achieved by treating sequences as permutations within a defined benchmark sequence. The paper details a method to calculate this ordinal number, which involves complex permutation and combination calculations. To improve efficiency, they propose an optimized method based on proportional relationships between permutation and combination values.

Furthermore, the paper explores parallelization using GPU computing to accelerate the ordinal calculation, demonstrating significant speedups for longer sequences. UCC is also presented as a "tree coding" method, where sequences can be mapped onto a tree structure. It's also framed as a "dictionary coding" method, where sequences are assigned positions within a pre-defined dictionary space. Finally, it's linked to "arithmetic coding" by representing sequences with an integer ordinal value, which is argued to be more accurate and precise than the [0, 1] range used in traditional arithmetic coding.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic descriptions, with experimental results presented in terms of computational time and speedup on synthetic sequence lengths rather than specific datasets.

Key Insights and Ideas

  • Unifying Principle: The paper proposes that a universal coding method exists, acting as a bridge between source, channel, and secrecy coding, which UCC aims to embody.
  • Probability Independence: UCC's strength lies in its independence from the statistical properties (probability distribution) of the information source, making it robust to unknown or changing source characteristics.
  • Combinatorial Foundation: By grounding itself in combinatorics, UCC offers a systematic way to assign unique identifiers (ordinals) to sequences, enabling diverse applications.
  • GPU Acceleration: The authors demonstrate that UCC's computational intensity can be effectively managed through parallel processing on GPUs, leading to substantial performance gains for longer sequences.
  • Precision in Representation: UCC's use of integer ordinals is presented as a more precise representation compared to the [0, 1] range in traditional arithmetic coding, especially for compression.
  • Multifaceted Applications: The paper highlights UCC's potential in combinatorial compression, encryption (with a large key space), and error detection, showcasing its versatility.

Key Results

  • Theoretical Efficiency: Theoretical analysis suggests that the average code length in UCC approaches the source entropy limit as the sequence length increases.
  • GPU Speedup: Figure 2 shows a significant speedup in ordinal computation using GPU parallel technology, with the speedup increasing with sequence length. Figure 1 illustrates that GPU computation time becomes less than CPU time for sequences longer than 64K.
  • Large Key Space for Encryption: UCC's combinatorial encryption method, using code elements instead of bits, generates a significantly larger key space (e.g., (2^6)! for m=6) compared to traditional bit-based encryption algorithms.
  • Accurate Ordinal Calculation: UCC provides a precise integer ordinal for sequences, which is argued to be more accurate than the relative position values used in traditional arithmetic coding.

Limitations and Future Work

  • Computational Complexity: The initial combinatorial calculation method is noted as having high computational complexity, necessitating optimization techniques like the proportional method and GPU parallelization.
  • Frequency Recording: While probability-independent, UCC still requires recording frequency values for each element, which is a drawback.
  • Approximate Calculation: The theoretical efficiency assessment involves approximate calculations, and the authors acknowledge that actual coding efficiency might be better than these estimates.
  • Further Research: The paper suggests that UCC has theoretical research and practical application value, implying that further exploration and development are warranted. The authors also mention that the method can be used for data validation and information abstracts, indicating potential for more advanced applications.

Summary updated

Abstract

The conception of universal combinatorial coding is proposed. Relations exist more or less in many coding methods. It means that a kind of universal coding method is objectively existent. It can be a bridge connecting many coding methods. Universal combinatorial coding is lossless and it is based on the combinatorics theory. The combinational and exhaustive property make it closely related with the existing code methods. Universal combinatorial coding does not depend on the probability statistic characteristic of information source, and it has the characteristics across three coding branches. It has analyzed the relationship between the universal combinatorial coding and the variety of coding method and has researched many applications technologies of this coding method. In addition, the efficiency of universal combinatorial coding is analyzed theoretically. The multicharacteristic and multiapplication of universal combinatorial coding are unique in the existing coding methods. Universal combinatorial coding has theoretical research and practical application value.
BibTeX
@article{lu2014research,
  author = {Jun Lu and Zhuo Zhang and Juan Mo},
  title = {{Research on Universal Combinatorial Coding}},
  journal = {The Scientific World JOURNAL},
  year = {2014},
  doi = {10.1155/2014/414613},
}
Figure