Every time data crosses a noisy channel (mobile networks, satellite links, Wi-Fi, even a hard disk), some bits get flipped. Channel coding adds controlled redundancy so the receiver can detect and correct those errors. A basic way to classify error-control codes is systematic vs non-systematic. This post explains both with clear examples, works through the classic (7,4) Hamming code with an animation, and ends with exam MCQs for EEE/ETE job tests (BTCL, Teletalk, Bangladesh Betar, BCS) and university exams.
- An (n, k) block code maps k message bits → n code bits; it adds n − k parity bits. Code rate R = k/n.
- Systematic code: the k message bits appear unchanged inside the codeword, followed or preceded by parity bits.
- Non-systematic code: the message bits are mixed into the codeword and are not directly visible.
- Systematic generator matrix: G = [Ik | P]; parity-check matrix: H = [PT | In−k]; syndrome s = r·HT.
- Hamming code: n = 2m − 1, k = n − m, dmin = 3. It corrects 1 error or detects 2.
1. Why Channel Coding?
Source coding (e.g. Huffman) removes redundancy to compress data. Channel coding adds redundancy in a structured way so errors can be found and fixed. There are two strategies:
- FEC (forward error correction): the receiver corrects errors itself, with no retransmission. Used in satellite, broadcast and deep-space links.
- ARQ (automatic repeat request): the receiver only detects errors (e.g. with a CRC) and asks for retransmission. Used in TCP and Wi-Fi.
The price of coding is bandwidth or data rate: a rate-4/7 code sends 7 bits for every 4 message bits.
2. Systematic vs Non-Systematic Codes
Systematic code: the codeword is made of the original message bits, unchanged, plus separately calculated parity (check) bits:
c = [ m1 m2 … mk | p1 p2 … pn−k ]The receiver can read the message straight from the codeword. After error correction, no extra decoding step is needed.
Non-systematic code: every code bit is a combination of several message bits, so the message cannot be read directly. It must be recovered by decoding (e.g. division by the generator polynomial, or Viterbi decoding for convolutional codes).
Both kinds can have the same error-correcting power for block codes. Any linear block code can be converted to an equivalent systematic form by row operations on G. For convolutional codes, non-systematic (feed-forward) codes usually give a larger free distance, so they are common in practice (e.g. the classic rate-1/2, constraint-length 7 code). Turbo codes use recursive systematic convolutional encoders.
3. (7,4) Hamming Code — Systematic Encoding and Error Correction
Take m = 3 parity bits: n = 2³ − 1 = 7 and k = 7 − 3 = 4. We use a systematic generator with these parity equations (⊕ = XOR, i.e. modulo-2 addition):
p1 = d1 ⊕ d2 ⊕ d3 p2 = d2 ⊕ d3 ⊕ d4 p3 = d1 ⊕ d2 ⊕ d4
Encoding message 1001 (d1d2d3d4): p1 = 1⊕0⊕0 = 1, p2 = 0⊕0⊕1 = 1, p3 = 1⊕0⊕1 = 0. The codeword is 1001 110; the first four bits are the message itself, which is what makes the code systematic.
In matrix form, with G = [I4 | P] and H = [PT | I3]:
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
Decoding: suppose d3 is flipped and 1011 110 is received. Recalculating the checks:
s1 = p1⊕d1⊕d2⊕d3 = 1, s2 = p2⊕d2⊕d3⊕d4 = 1, s3 = p3⊕d1⊕d2⊕d4 = 0The syndrome is 110, which is the third row of P (the column of d3 in H). Flipping d3 restores 1001 110. A zero syndrome means no detectable error. Because the 7 non-zero syndromes match the 7 bit positions one-to-one, the Hamming code is a perfect code: it meets the Hamming bound 2n−k = n + 1 exactly.
4. Cyclic Code Example: Systematic and Non-Systematic
The (7,4) cyclic Hamming code uses the generator polynomial g(x) = 1 + x + x³. Take the message m = 1001, i.e. m(x) = 1 + x³ (coefficients m0 … m3).
Non-systematic encoding: c(x) = m(x)·g(x) = (1 + x³)(1 + x + x³) = 1 + x + x⁴ + x⁶ (modulo-2, the two x³ terms cancel). The codeword c0…c6 = 1100101; the message 1001 cannot be seen in it.
Systematic encoding: shift the message by n − k = 3 places, divide by g(x) and append the remainder:
x³m(x) = x³ + x⁶; remainder of (x³ + x⁶) ÷ g(x) = x + x²c(x) = x + x² + x³ + x⁶ ⟹ c0…c6 = 011 | 1001
The last four bits are the message 1001 and the first three are parity. Both codewords belong to the same code, since both are multiples of g(x). In hardware, systematic cyclic encoding is done with a simple shift register with feedback. This is exactly how a CRC is generated.
5. Comparison Table
| Feature | Systematic code | Non-systematic code |
|---|---|---|
| Message bits in codeword | Appear unchanged | Mixed / transformed |
| Generator matrix | G = [Ik | P] | General form |
| Extracting message | Read directly (after correction) | Needs full decoding |
| Encoder/decoder complexity | Simpler | Usually more complex |
| Error-correcting power (block codes) | Same as an equivalent non-systematic code | Same |
| Typical examples | Systematic Hamming, CRC, Reed–Solomon (usual systematic form), turbo codes | m(x)g(x) cyclic codes, feed-forward convolutional codes |
6. Important Terms and Formulas
| Term | Meaning / formula |
|---|---|
| Code rate | R = k/n (Hamming (7,4): 4/7 ≈ 0.57) |
| Redundancy | n − k parity bits |
| Hamming weight | Number of 1s in a codeword |
| Hamming distance | Number of positions in which two codewords differ |
| Minimum distance dmin | Smallest distance between any two codewords (= minimum weight for linear codes) |
| Error detection | Detects up to dmin − 1 errors |
| Error correction | Corrects up to t = ⌊(dmin − 1)/2⌋ errors |
| Hamming bound (single error) | 2n−k ≥ n + 1 |
7. Practice MCQs
1. In a systematic code, the message bits: (a) Are encrypted (b) Appear unchanged in the codeword (c) Are deleted (d) Are inverted
2. The code rate of a (15, 11) Hamming code is: (a) 11/15 (b) 15/11 (c) 4/15 (d) 4/11
3. Minimum distance of a Hamming code is: (a) 1 (b) 2 (c) 3 (d) 4
4. A code with dmin = 5 can correct up to: (a) 1 error (b) 2 errors (c) 4 errors (d) 5 errors
5. The generator matrix of a systematic (n, k) code has the form: (a) [P | P] (b) [Ik | P] (c) [In] (d) [H | G]
6. For m = 4 parity bits, a Hamming code has n = ? (a) 7 (b) 15 (c) 16 (d) 31
7. A zero syndrome indicates: (a) Burst error (b) No detectable error (c) Two errors (d) Decoder failure
8. The Hamming distance between 1011101 and 1001001 is: (a) 1 (b) 2 (c) 3 (d) 4
9. Which code family uses recursive systematic convolutional encoders? (a) Huffman (b) Turbo codes (c) Manchester (d) Gray code
10. Channel coding mainly aims to: (a) Compress data (b) Add redundancy to control errors (c) Encrypt data (d) Increase bandwidth efficiency
8. বাংলায় দ্রুত রিভিশন
- সিস্টেম্যাটিক কোড: কোডওয়ার্ডে মূল মেসেজ বিট অপরিবর্তিত থাকে, সঙ্গে প্যারিটি বিট যোগ হয়।
- নন-সিস্টেম্যাটিক কোড: মেসেজ বিট মিশে যায়, সরাসরি পড়া যায় না; ডিকোড করতে হয়।
- (n, k) কোডে কোড রেট = k/n; প্যারিটি বিট = n − k।
- সিস্টেম্যাটিক জেনারেটর ম্যাট্রিক্স G = [I | P]; সিনড্রোম s = rHᵀ; s = 0 হলে ভুল নেই।
- হ্যামিং কোড: n = 2ᵐ − 1, dmin = ৩; একটি ভুল সংশোধন বা দুটি ভুল শনাক্ত করতে পারে।
- সংশোধন ক্ষমতা t = ⌊(dmin − 1)/2⌋; শনাক্তকরণ ক্ষমতা = dmin − 1।
Related Posts
- Channel Coding vs Source Coding
- Huffman Coding with Examples
- Line Coding: NRZ, RZ, AMI, Manchester
- Eye Diagram in Digital Communication
- Mostly Asked Communication Systems MCQs
References: Simon Haykin, Communication Systems; Shu Lin & Daniel J. Costello, Error Control Coding; B. P. Lathi, Modern Digital and Analog Communication Systems. Images and animations: original work by Totalecer.