Implementation of (21,16) Hamming code for error detection and correction in digital communications. Features bitwise operations, parity bit calculation, and interactive encoding/decoding with comprehensive binary and hexadecimal data visualization.
The Hamming code is a linear error-correcting code that can detect and correct single-bit errors in transmitted data. This implementation uses a (21,16) Hamming code, meaning it encodes 16 information bits into a 21-bit codeword by adding 5 parity bits at specific positions.
- 16-bit input: Encodes two ASCII characters (8 bits each)
- Parity bit insertion: Adds 5 parity bits at positions 1, 2, 4, 8, 16
- Error detection capability: Can detect single and double-bit errors
- Error correction capability: Can correct single-bit errors
- Hex input: Accepts 6-digit hexadecimal codewords
- Information extraction: Recovers original 16-bit data
- ASCII conversion: Converts back to original character pair
- Visual feedback: Shows binary representation with bit position markers
- Command-line driven: Simple encode/decode/exit commands
- Visual output: Binary representation with bit groupings
- Comprehensive display: Shows parity bits, hex values, and ASCII characters
- Error handling: Input validation and format checking
The (21,16) Hamming code places parity bits at positions that are powers of 2:
- Position 1: Parity bit P1
- Position 2: Parity bit P2
- Position 4: Parity bit P4
- Position 8: Parity bit P8
- Position 16: Parity bit P16
Each parity bit covers positions whose binary representation includes that bit:
- P1: Covers positions with bit 1 set (1,3,5,7,9,11,13,15,17,19,21)
- P2: Covers positions with bit 2 set (2,3,6,7,10,11,14,15,18,19)
- P4: Covers positions with bit 4 set (4,5,6,7,12,13,14,15,20,21)
- P8: Covers positions with bit 8 set (8,9,10,11,12,13,14,15)
- P16: Covers positions with bit 16 set (16,17,18,19,20,21)
gcc -Wall -g -std=c99 p3.c -o hamming_code./hamming_codeEnter command: encode A B
Encoding characters: 'A' and 'B'
Information word (hex): 0x4241
Information word (binary): 0100 0010 0100 0001
Parity bits:
P1 (bit 1): 0
P2 (bit 2): 1
P4 (bit 4): 1
P8 (bit 8): 0
P16 (bit 16): 1
Encoded codeword (hex): 0x108486
Encoded codeword (binary): ---100 0010 0001 0100 1000 0110
Enter command: decode 108486
Decoding codeword: 108486
Hex digits: 1 0 8 4 8 6
Binary representation: ---100 0010 0001 0100 1000 0110
^ ^ ^^ ^ ^^ ^ ^^^ ^
Extracted information word (binary): 0100 0010 0100 0001
Extracted information word (hex): 42 41
Decoded ASCII characters: 'B' 'A'
Enter command: exit
Exiting program.
- Position-based encoding: Uses bit positions 1-21 (1-indexed)
- Parity calculation: XOR operations for even parity
- Bit extraction: Selective bit copying without arrays
- Binary visualization: Formatted output with nibble grouping
1. Initialize 21-bit codeword to zero
2. Insert 16 information bits into non-parity positions
3. For each parity position (1,2,4,8,16):
a. Calculate XOR of all covered positions
b. Set parity bit to achieve even parity
4. Return complete 21-bit codeword1. Extract bits from non-parity positions
2. Reconstruct 16-bit information word
3. Convert to ASCII characters
4. Display results with formatting- No bit arrays: Uses bitwise operations exclusively
- Minimal storage: Single variables for codewords
- Stack-based: No dynamic memory allocation
- Efficient operations: Direct bit manipulation
The syndrome calculation can identify and correct single-bit errors:
Syndrome = P1 ⊕ P2 ⊕ P4 ⊕ P8 ⊕ P16
- Syndrome = 0: No error detected
- Syndrome ≠ 0: Points to error position
- Single-bit errors: Detectable and correctable
- Double-bit errors: Detectable but not correctable
- Multiple errors: May cause incorrect correction
Input: 'H' (0x48) and 'i' (0x69)
16-bit word: 0x6948
Binary: 0110 1001 0100 1000
Codeword positions (21 bits):
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
0 1 1 0 1 P 0 0 1 0 1 0 0 P 1 0 0 P 0 P P
Parity calculations:
P1 = 0, P2 = 1, P4 = 1, P8 = 0, P16 = 1
Final codeword: 0x0D484E
- Network protocols: Error detection in data transmission
- Storage systems: Data integrity in memory and disk
- Wireless communication: Error correction in noisy channels
- ECC RAM: Error correction in memory systems
- Cache coherency: Data integrity in processor caches
- Disk storage: Error correction in hard drives
- Time: O(1) - Fixed number of operations
- Space: O(1) - Constant memory usage
- Bit operations: ~50 bitwise operations per encoding
- Time: O(1) - Fixed extraction process
- Space: O(1) - No additional storage
- Reconstruction: Direct bit copying
- Error correction theory: Understanding Hamming codes
- Bitwise operations: Advanced bit manipulation in C
- Digital communications: Practical error correction
- Binary representation: Low-level data visualization
- Parity concepts: Even/odd parity calculations
- Bit manipulation: Mastery of bitwise operators
- Data encoding: Information to codeword conversion
- Format conversion: Binary, hex, and ASCII display
- Interactive programming: Command-line interface design
Aidan Fernandes
ECE 2220 - Spring 2025
Clemson University
This project demonstrates:
- Classical error correction coding theory
- Bitwise programming techniques in C
- Digital communications principles
- Interactive command-line application design
- Data visualization and formatting