Design of a Data Compression and Integrity Assurance Scheme Based on Communication Coding Theory¶

Authors: Lin Zhiyang, Wang Xiao, Zhang Daoyou

Keywords: source coding; Huffman coding; channel coding; cyclic redundancy check; Hamming code; data integrity

1 Introduction¶

The core task of a digital communication system is to improve the efficiency of information transmission and storage as far as possible while guaranteeing the accuracy of the information. According to Shannon's information theory, the model of a digital communication system generally consists of a source, source coding, channel coding, a channel (with noise), channel decoding, source decoding and a sink. Within this model, the system currently faces two fundamental challenges:

1. Data validity: raw data usually contains a large amount of statistical redundancy, and storing or transmitting it directly consumes excessive bandwidth and storage resources.
2. Data reliability and integrity: physical channels (such as wireless networks, optical fibre links and storage media) are inevitably subject to noise interference, and data is highly prone to bit flips or corruption during transmission or storage, which causes the data to become unusable.

In response to the above challenges, this paper designs a closed-loop algorithmic scheme from the two dimensions of "source coding" and "channel coding", so as to solve the practical engineering problems of data compression and data integrity assurance. The main work of this paper includes: reviewing the mathematical basis and constraint conditions of the two coding levels; clarifying the concatenation order of the compression layer and the error-correction layer and their mutual influence; and providing a reproducible simulation-based verification path and evaluation metrics.

2 Source Coding: A Data Compression Scheme Based on Huffman Coding¶

2.1 Theoretical Basis and Objectives¶

The core objective of source coding is to solve the problem of compressing data well, that is, to represent information with as few bits as possible by removing source redundancy, thereby improving transmission and storage efficiency.

Let the symbol set of a source X be {x₁, x₂, …, xₘ}, and let the occurrence probability of each symbol be pᵢ; the source entropy is then defined as

H(X) = − Σᵢ pᵢ log₂ pᵢ        (i = 1, 2, …, m; in bit/symbol)

By the source coding theorem (the lossless coding theorem), the average codeword length L of any lossless code must satisfy L ≥ H(X). The coding efficiency η is defined as

η = H(X) / L × 100%

Clearly 0 < η ≤ 1; the closer η is to 1, the higher the utilisation of the codewords with respect to the source symbols, and the better the compression effect.

2.2 Algorithm Selection and Logical Consistency¶

In order to approach the theoretical limit, this scheme selects Huffman coding as the core compression algorithm. Huffman coding is an algorithm that constructs an optimal prefix code on the basis of symbol occurrence probabilities, and its logical consistency is reflected in the following:

1. Characters that occur frequently are assigned shorter binary codewords;
2. Characters that occur infrequently are assigned longer binary codewords.

Since no codeword is a prefix of any other codeword (that is, the prefix-code condition is satisfied), there is no ambiguity during decoding, and the code stream can be split uniquely without any separator. It can be proved that, for a given symbol probability distribution, the average codeword length L of Huffman coding is the smallest among all prefix codes and satisfies H(X) ≤ L < H(X) + 1; it is therefore the optimal code approaching the source entropy. The algorithm is suitable for scenarios with pronounced statistical characteristics, such as text files and sensor-acquired data.

It should be pointed out that the effectiveness of Huffman coding depends on the non-uniformity of the source symbol probability distribution: when the data is approximately uniformly distributed, or when its statistical properties change rapidly (non-stationary), the compression gain drops markedly, and negative compression may even occur because of the overhead of the code table. In addition, the compressed code stream is very sensitive to channel errors — once a bit misalignment occurs during the decoding of a variable-length code, the error propagates backwards along the code stream, causing damage far greater than the range of the original error; this is the phenomenon of "error propagation". It is precisely this characteristic that makes it necessary to introduce channel coding after compression in the next chapter, and to ensure that the error-correction layer is completed before source decoding.

3 Channel Coding: An Integrity Assurance Scheme Based on CRC and Hamming Code¶

3.1 Theoretical Basis and Objectives¶

The core objective of channel coding is to solve the problem of transmitting data accurately and storing it correctly. Unlike source coding, which removes redundancy, channel coding must actively add controllable redundancy so that the receiving end can detect and even correct errors caused by channel noise. The core metrics for evaluating the performance of a channel code include the code rate R = k/n (where k is the information bit length and n is the total codeword length) and the minimum Hamming distance dmin. From the relationship between the minimum Hamming distance and the error correction/detection capability, it follows that:

Detecting e errors requires            dmin ≥ e + 1
Correcting t errors requires            dmin ≥ 2t + 1
Correcting t and detecting e errors  dmin ≥ t + e + 1   (e > t)

The above three relations are the theoretical basis for selecting the specific error-correcting code type and determining the number of parity bits later in this paper.

3.2 Algorithm Selection and Logical Consistency¶

In order to balance data integrity and error recovery capability, this scheme adopts a concatenated strategy of cyclic redundancy check (CRC) and Hamming code. The division of labour and the order between the two are as follows: the Hamming code takes on error correction, while the CRC takes on error detection and integrity confirmation, and the receiving end corrects errors first and checks afterwards.

(1) CRC cyclic redundancy check (used for error detection)

CRC is implemented on the basis of modulo-2 polynomial division. Let the information polynomial to be transmitted be M(x) and the generator polynomial be G(x); the check code is then given by

M(x) · xʳ mod G(x) = R(x)        (r is the highest power in G(x))

and the codeword actually transmitted is M(x)·xʳ ⊕ R(x). The receiving end performs modulo-2 division by G(x) on the received codeword once more: if the remainder is zero, the block is judged to be error-free; if it is non-zero, an error is judged to have occurred and the data block is marked as unusable. The error-detection capability of CRC depends on the choice of the generator polynomial; when a primitive polynomial or a generator polynomial conforming to international standards (such as the G(x) of CRC-32) is selected, all single-bit and double-bit errors as well as burst errors no longer than r bits can be detected, which is why CRC is widely used in Ethernet, USB and storage systems.

It should be noted that CRC is an error-detection mechanism aimed at random and burst errors, and is not an anti-tampering measure in the cryptographic sense: an attacker can modify the data while recomputing and replacing the CRC check code without being detected. If the system faces an active tampering threat, a cryptographic hash such as SHA-256 or a message authentication code (MAC) should additionally be introduced to guarantee integrity, and CRC must not be relied upon.

(2) Hamming code (used for error correction)

The Hamming code is a classic linear block code that protects k data bits by adding r parity bits, giving a codeword length of n = k + r. Its parity bits and data bits must satisfy the constraint 2ʳ ≥ k + r + 1, that is, the length of the parity bits grows logarithmically as the data bits grow. The core advantage of the Hamming code lies in its ability to locate and correct single-bit errors: the syndrome constructed from the n-bit codeword indicates exactly the position of the error, and XORing that position completes the correction. When a single bit flip occurs in a storage medium, the Hamming code can repair the data automatically without requesting retransmission, thereby reducing retransmission overhead and latency.

This also brings a limitation that must be confronted squarely: the basic Hamming code (dmin = 3) can correct only 1 bit; when a 2-bit error occurs, the syndrome is misinterpreted as the position of some single-bit error, so that an erroneous codeword is "corrected" into another valid codeword, causing error expansion more serious than no correction at all. To avoid this risk, this scheme adopts the extended Hamming code (SECDED, single-error correction—double-error detection), that is, one additional overall parity bit is added so that dmin = 4, thereby obtaining the ability to correct 1-bit errors and detect 2-bit errors at the cost of only one extra redundant bit, while the detected uncorrectable errors are handed over to the CRC and the upper-layer retransmission mechanism.

(3) Concatenated structure and parameters

The concatenation order is "Huffman coding → (blocking) → Hamming coding → CRC coding", and the decoding order is the reverse, namely "CRC check → Hamming decoding → Huffman decoding". Suppose the code stream after Huffman coding is divided into data blocks of length k bits; after Hamming coding each block has length n = k + r, and an rc-bit CRC check code is then appended. The total code rate of the system is then

Rtotal = k / (k + r + rc)

This expression shows that error-correction and error-detection capability is obtained at the cost of the code rate (that is, the proportion of useful data): the bits saved by the compression layer are partially consumed by the error-correction layer, and the trade-off between the two must be evaluated quantitatively in simulation. In addition, in order to eliminate the problem of whole-block failure caused by consecutive bits being corrupted at the same time, a practical system must also introduce interleaving after Hamming coding, and periodically insert frame synchronisation markers into the code stream, so that the receiving end can block the data correctly and avoid large-area decoding errors caused by loss of synchronisation.

(4) Handling of burst errors

For burst errors that may occur in long-distance transmission or in storage media, the error-correction capability of the Hamming code and interleaving alone is limited. In subsequent work, convolutional codes, Reed-Solomon codes or LDPC codes, which are better suited to combating burst errors, may be introduced; a simple parity check provides only single-bit error detection and cannot locate the error, so it is not suitable as a supplement for burst errors and is therefore not adopted in this scheme.

4 System Implementation and Interactive Verification Path¶

In order to bring the theoretical scheme into practice and make it reproducible, this paper will carry out system implementation and verification on an interactive course demonstration platform according to the following steps.

4.1 Verification Steps¶

1. System modelling: build a basic digital communication simulation environment comprising a source, an encoder, a noisy channel and a sink, and specify that the channel is a binary symmetric channel (BSC) model, whose crossover probability p represents the bit error rate.
2. Compression-layer verification: input raw text data (it is recommended to use one group each of Chinese text, English text and a random bit string, so as to cover both non-uniform and near-uniform distributions), count the symbol frequencies and construct the Huffman tree, observe the compression process from text to bit stream, compute the average codeword length L, the source entropy H(X) and the coding efficiency η, and record the compression ratio.
3. Superposition of the coding layers: divide the compressed bit stream into blocks of fixed length, apply Hamming (SECDED) coding first, then compute and append the CRC check code, while also recording the frame synchronisation markers and the interleaving depth.
4. Noise injection and error-correction simulation: flip bits randomly in the channel according to a set probability to simulate transmission errors (burst errors may also be simulated in order to test the effect of interleaving). The receiving end performs channel decoding in sequence (the CRC check determines whether the block is trustworthy, and Hamming decoding corrects single-bit errors and detects double-bit errors); only after confirming that the data is error-free does it carry out source decoding (Huffman decoding) and restore the original file. For blocks judged uncorrectable, their positions are recorded and the extent of error propagation is measured.
5. Performance evaluation: through multiple groups of simulations, quantitatively evaluate the code rate R, the minimum Hamming distance dmin, the compression ratio, the end-to-end data restoration accuracy, the block error rate (BLER) and the curve of the uncorrectable error rate against the channel bit error rate p.

4.2 Evaluation Metrics and Expectations¶

Table 1 summarises the evaluation metrics corresponding to each coding level and their physical meaning. The minimum Hamming distance is an intrinsic property of the code type and is determined directly by the chosen code; the remaining metrics must be obtained through simulation statistics.

Note: the specific values of the above expected metrics must be measured by the simulation experiments in Section 4.1. Before the experimental data is complete, this paper does not give quantitative conclusions on the compression gain or the error-correction gain.

4.3 Application Analysis in Optical Communication Scenarios¶

(1) Optical communication system model and channel characteristics

Optical communication is a mode of communication that uses light waves as the carrier and optical fibre as the transmission medium. It offers advantages such as large bandwidth, low loss and strong resistance to electromagnetic interference, and has become a core transmission technology for modern backbone networks, data-centre interconnection and submarine cables. A typical digital optical fibre communication system consists of an optical transmitter (laser and modulator), an optical fibre link (including optical amplifiers) and an optical receiver (photodetector and decision circuit). When an intensity modulation with direct detection (IM-DD) scheme such as on-off keying (OOK) is adopted, the electrical signal before the decision at the receiving end can be approximated as a binary waveform affected by additive noise, and after sampling and decision it corresponds to the binary symmetric channel (BSC) model described in this paper, whose crossover probability p can be estimated analytically from the optical signal-to-noise ratio (OSNR) or the received optical power.

(2) Main impairments and noise sources of the optical channel

The impairment mechanisms of an optical fibre channel differ from those of a wireless channel and mainly include attenuation, chromatic dispersion, polarisation mode dispersion and fibre nonlinear effects (such as self-phase modulation, cross-phase modulation and four-wave mixing); the noise, on the other hand, originates from shot noise and thermal noise in the photodetection process, as well as the amplified spontaneous emission (ASE) noise introduced by erbium-doped fibre amplifiers (EDFAs). Among these, dispersion and nonlinear effects cause inter-symbol interference, giving the bit errors a certain burst character, whereas ASE noise and shot noise are closer to random errors. This characteristic is consistent with the approach of classifying and handling random errors and burst errors in Chapter 3 of this paper.

(3) Adaptation of the coding scheme to optical communication

Optical communication systems generally adopt forward error correction (FEC) as a standard technology; for example, ITU-T G.975.1 defines ultra-strong FEC schemes such as RS(255,239), concatenated codes and LDPC, with typical net coding gains of 8–10 dB. For short-reach, low-latency scenarios (such as data-centre optical interconnects), the "Hamming code (SECDED) + CRC" concatenated structure proposed in this paper has the advantages of low encoding/decoding complexity and small processing latency, and is suitable for providing basic data integrity assurance under constrained redundancy overhead (for example ≤7%); for long-haul trunk scenarios, the Hamming code should be replaced by a Reed-Solomon code or an LDPC code as described in Section 3.2 (4), so as to obtain stronger random and burst error correction capability. In addition, dispersion compensation and polarisation management in optical communication systems can effectively suppress burst errors, and are complementary to the interleaving technique of this scheme.

(4) Optical communication mapping of the verification parameters

When carrying out simulation verification for optical communication scenarios, the crossover probability p of the binary symmetric channel can be replaced by an equivalent bit error rate model, and the received optical power or the OSNR can be used as the sweep variable, plotting the compression ratio, the block error rate (BLER) and the uncorrectable error rate against the OSNR, so as to evaluate the operating boundary and applicable scenarios of this scheme under a typical optical link budget.

4.4 C Language Implementation of the Core Algorithms¶

In order to verify the engineering feasibility of the algorithms designed in Chapters 2 and 3, this paper provides reference C implementations of three core modules: Huffman coding, the CRC cyclic redundancy check, and the Hamming code (SECDED). The following code is based on bit operations and omits engineering details such as memory allocation checks and input validity checks, focusing on the algorithm logic itself.

(1) Huffman coding

First, the Huffman tree is constructed by merging from the bottom up according to the symbol frequencies; then the prefix codeword of each symbol is generated by tracing backwards from the leaves to the root. The core code is as follows:

/* Huffman tree node */
typedef struct {
    unsigned char symbol;     /* source symbol        */
    unsigned long freq;       /* symbol frequency     */
    int parent, lchild, rchild;
} HTNode;

/* Pick the two lowest-frequency nodes with parent == -1 in ht[0..m-1] */
static void select_two_min(HTNode ht[], int m, int *s1, int *s2)
{
    *s1 = *s2 = -1;
    for (int i = 0; i < m; i++) {
        if (ht[i].parent != -1) continue;
        if (*s1 == -1 || ht[i].freq < ht[*s1].freq) {
            *s2 = *s1; *s1 = i;
        } else if (*s2 == -1 || ht[i].freq < ht[*s2].freq) {
            *s2 = i;
        }
    }
}

/* Build the Huffman tree from n symbol frequencies (2n-1 nodes) */
void huffman_build(HTNode ht[], int n)
{
    int m = 2 * n - 1;
    for (int i = n; i < m; i++) {              /* n-1 merges in total */
        int s1, s2;
        select_two_min(ht, i, &s1, &s2);
        ht[i].freq   = ht[s1].freq + ht[s2].freq;
        ht[i].lchild = s1;  ht[i].rchild = s2;
        ht[s1].parent = ht[s2].parent = i;
    }
}

/* Walk leaf to root to build each symbol's Huffman codeword */
void huffman_code(HTNode ht[], char *code[], int n)
{
    char *buf = malloc(n);
    for (int i = 0; i < n; i++) {
        int len = 0, c = i, p = ht[i].parent;
        while (p != -1) {                      /* left branch = 0, right branch = 1 */
            buf[len++] = (ht[p].lchild == c) ? '0' : '1';
            c = p;  p = ht[p].parent;
        }
        code[i] = malloc(len + 1);
        for (int j = 0; j < len; j++)          /* store in reverse to get the codeword */
            code[i][j] = buf[len - 1 - j];
        code[i][len] = '\0';
    }
    free(buf);
}

(2) CRC cyclic redundancy check

At the encoding end, M(x)·x^r is divided by the generator polynomial G(x) using modulo-2 division, and the resulting r-bit remainder is appended and transmitted as the check code; at the receiving end, the received codeword is divided by G(x) once more, and if the remainder is zero the block is judged to be error-free. The core code is as follows:

/* Index of the highest set bit of v */
static int msb_pos(unsigned int v)
{
    int pos = -1;
    while (v) { v >>= 1; pos++; }
    return pos;
}

/* Modulo-2 division: remainder of dividend by the generator poly */
unsigned int crc_remainder(unsigned int dividend, unsigned int poly)
{
    int d;
    while ((d = msb_pos(dividend) - msb_pos(poly)) >= 0)
        dividend ^= poly << d;    /* XOR is modulo-2 subtraction */
    return dividend;
}

/* CRC encode: the remainder of M(x)*x^r is the r-bit check R(x) */
unsigned int crc_encode(unsigned int data, unsigned int poly, int r)
{
    return crc_remainder(data << r, poly);
}

/* CRC check: remainder 0 means no error, non-zero means error */
int crc_check(unsigned int codeword, unsigned int poly)
{
    return crc_remainder(codeword, poly) == 0;
}

(3) Hamming code (SECDED)

At the encoding end, the data bits are placed in the non-power-of-two positions in sequence, and the parity bits are then computed and placed; at the decoding end, the parity bits are recomputed to obtain the syndrome, and when the syndrome is non-zero its value is precisely the error position, so flipping that bit completes the correction. The core code is as follows:

/* Hamming encode: r parity bits for k data bits, length n = k + r */
unsigned int hamming_encode(unsigned int data, int k, int r)
{
    unsigned int cw = 0;
    int j = 0;
    for (int i = 1; i <= k + r; i++) {
        if (i & (i - 1))                       /* non-power-of-two positions hold data bits */
            cw |= ((data >> j++) & 1u) << (i - 1);
    }
    for (int i = 0; i < r; i++) {              /* compute each parity bit */
        int p = 1 << i, parity = 0;
        for (int t = 1; t <= k + r; t++)
            if (t & p) parity ^= (cw >> (t - 1)) & 1u;
        cw |= (unsigned int)parity << (p - 1); /* store at position 2^i */
    }
    return cw;
}

/* Hamming decode: locate and correct a single-bit error from the syndrome */
unsigned int hamming_decode(unsigned int cw, int n, int *err_pos)
{
    int syndrome = 0;
    for (int i = 0; (1 << i) <= n; i++) {
        int p = 1 << i, parity = 0;
        for (int t = 1; t <= n; t++)
            if (t & p) parity ^= (cw >> (t - 1)) & 1u;
        syndrome |= parity << i;
    }
    *err_pos = syndrome;                       /* non-zero = error position */
    if (syndrome)
        cw ^= 1u << (syndrome - 1);            /* flip that bit to correct it */
    return cw;
}

The above three modules are called in sequence according to the concatenation order determined in Section 3.2: the transmitting end performs Huffman coding, blocking, Hamming coding and CRC coding in turn, while the receiving end performs the CRC check, Hamming decoding and Huffman decoding in the reverse order, thus forming a complete "compression—coding—transmission—decoding—restoration" link and providing the implementation basis for the simulation verification in Section 4.1.

5 Conclusion and Outlook¶

Based on the basic model of a digital communication system, this paper constructs a coding scheme that integrates data compression and integrity assurance. On the source-coding side, Huffman coding is chosen to remove statistical redundancy, so that the average codeword length approaches the source entropy in theory; on the channel-coding side, a concatenated structure of the Hamming code (SECDED) and CRC is adopted, correcting errors first and checking afterwards, so as to take on the responsibilities of error recovery and integrity confirmation respectively. This paper further clarifies the quantitative relationships among the concatenation order, the parity-bit constraint and the total code rate, and points out that the error-propagation characteristics of the compression layer and the miscorrection risk of the basic Hamming code are two boundary conditions that must be handled in the design of the scheme.

It should be noted that what this paper has completed so far is scheme design and theoretical argumentation; the conclusions are all qualitative analyses and are not yet supported by experimental data. Subsequent work will focus on the implementation and performance tuning of the interactive demonstration system, running the full "compression—coding—noise—decoding—restoration" pipeline with real data, and will verify three things in particular: first, whether the net gain of the compression benefit over the error-correction redundancy overhead is positive; second, the actual extent of the influence of error propagation on end-to-end restoration; and third, the operating boundary of the system under a given channel bit error rate p. On this basis, the applicability of alternative schemes such as convolutional codes and Reed-Solomon codes in this scenario will be further compared. For the important application scenario of optical communication, subsequent work will also combine the scheme of this paper with the OSNR budget and dispersion compensation strategy of an optical link, so as to evaluate its actual performance in data-centre optical interconnects and long-haul optical fibre transmission.

References¶

1. SHANNON C E. A mathematical theory of communication[J]. The Bell System Technical Journal, 1948, 27(3): 379-423.
2. HUFFMAN D A. A method for the construction of minimum-redundancy codes[J]. Proceedings of the IRE, 1952, 40(9): 1098-1101.
3. HAMMING R W. Error detecting and error correcting codes[J]. The Bell System Technical Journal, 1950, 29(2): 147-160.
4. PETERSON W W, BROWN D T. Cyclic Codes for Error Detection[J]. Proceedings of the IRE, 1961, 49(1): 228-235.
5. WANG X M, XIAO G Z. Error-Correcting Codes: Principles and Methods[M]. Revised ed. Xi'an: Xidian University Press, 2001.
6. FU Z Y. Information Theory: Fundamentals and Applications[M]. 4th ed. Beijing: Publishing House of Electronics Industry, 2015.
7. LIN S, COSTELLO D J. Error Control Coding: Fundamentals and Applications[M]. 2nd ed. Upper Saddle River: Pearson Prentice Hall, 2004.
8. AGRAWAL G P. Fiber-Optic Communication Systems[M]. 4th ed. Hoboken: Wiley, 2010.
9. YUAN R. Optical Fiber Communications[M]. 3rd ed. Beijing: Publishing House of Electronics Industry, 2010.