Error Control Coding for Wireless Communication Technologies
Error control coding plays a crucial role in ensuring reliable communication over wireless networks. This background material delves into Hamming codes, specifically focusing on their application in the EU-USA Atlantis Programme in collaboration with FIT and Budapest University of Technology and Economics. The objective is to design a code capable of correcting every single error, with a detailed exploration of constructing Hamming codes like C(7,4) for achieving perfect error correction capability.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Error control coding for wireless communication technologies Background material for Hamming codes EU-USA Atlantis Programme FIT & Budapest University of Technology and Economics
Objective Design a code which can correct every single error. Motivation: If the channel is good then it is enough to have a limited error correcting capability.
Hamming codes Capable of correcting every single error, they are perfect codes: n k n k = = + = 2 n i 1 1 2 n n 1 n k n k + = 2 1 2 n = 0 i Construction of C(n,k) Hamming code: Construct the column vectors of the parity check matrix H by fulfilling that all column vectors must be different form each other and none of them can be the all zero vector 1. 2. Construct the generator matrix 3. Design the matching gates syndrome decoding 4. Implement the full scheme
The C(7,4) Hamming code n k 7 4 + = + = = 3 1 2 7 1 2 8 2 n Constructing the parity check matrix H 0 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 = H 3 7 x Constructing the generator matrix G 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 = G 4 7 x
Step 2: Constructing the parity check matrix H 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 0 0 = H 3 7 x 0 1 Step 3: Constructing the generator matrix G 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 = G 4 7 x
Constructing the matching system for decoding 2s 1s 3s ( ) 1 i a Match (1)/Mismatch (0) ( ) 2 i a ( ) 3 i a s ( ) i a Matching systems Match (1)/Mismatch (0)
( ) = (1) E.g. a 011 2s 1s 3s 0 Match (1)/Mismatch (0) 1 1 s Matching systems Match (1)/Mismatch (0) = (1) a (011)
( ) = (2) E.g. a 101 2s 1s 3s 1 Match (1)/Mismatch (0) 0 1 s Matching systems Match (1)/Mismatch (0) = (2) a (101)
( ) = (3) E.g. a 110 2s 1s 3s 1 Match (1)/Mismatch (0) 1 0 s Matching systems Match (1)/Mismatch (0) = (3) a (110)
( ) = (4) E.g. a 111 2s 1s 3s 1 Match (1)/Mismatch (0) 1 1 s Matching systems Match (1)/Mismatch (0) = (4) a (111)
( ) = (5) E.g. a 100 2s 1s 3s 1 Match (1)/Mismatch (0) 0 0 s Matching systems Match (1)/Mismatch (0) = (5) a (100)
( ) = (6) E.g. a 010 2s 1s 3s 0 Match (1)/Mismatch (0) 1 0 s Matching systems Match (1)/Mismatch (0) = (6) a (010)
( ) = (7) E.g. a 001 2s 1s 3s 0 Match (1)/Mismatch (0) 0 1 s Matching systems Match (1)/Mismatch (0) = (7) a (001)
Implementation Mathcing system (1) a Mathcing system e (2) a u v s Mathcing system H G (3) a bP BSC with e Mathcing system u c Trunc (4) a Mathcing system (5) a Mathcing system (6) a Mathcing system (7) a
The coding scheme s e 000 00000 00100 001 00001 100 01011 01111 01111 01 00100 010 00010 01 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 1 Trunc 011 00011 100 00100 101 00101 110 10000 111 01000
Bit error probability analysis ( ) ( ) ( ) e ( ) ( ) 1 n n = = receiving a message vector with error 1 1 1 1 P P w P nP P b b b Array off masking gates or LUT u H G Trunc bP BSC with BSC u' u ( ) k ( ) = ' receiving a message vector with error ) 1 1 b b P P = 1 1 P ( P b k ( ) ( ) ( ) 1 n n = ' ' 1 1 1 , , n k P nP P P b b b b ' Given a BSC with bP 10 bP it tells us how to choose n and k parameters to fulfill a given
The modified bit-error probability in the case as a function of code parameters in the case of P_b=0.01 Loss in data speed: 1/3; 4/7; 11/15; 57/63; 120/127; 247/255
The modified bit-error probability in the case as a function of code parameters in the case of P_b=0.001 Loss in data speed: 1/3; 4/7; 11/15; 57/63; 120/127; 247/255
Code design from the point of communication engineering , design a code which can achieve bP ' 10 bP Given a BSC with and a required level of QoS ( ) k ( ) ( ) ( ) 1 n n = then there is no solution with correcting only single errors = ' ' 1 1 1 1 1 , , n k P , P P nP P P n k 1. Evaluate b b b b b b if n-k is too large or if (then you need a more powerful code capable of correcting more than a single error) n k 2 1 n 2. Construct the parity check matrix obeying the rules: (i) each column vector is different; (ii) none of the column vector is the all-zero vector; (iii) the code is systematic 3. Implement the coding scheme Array of masking gates or LUT u H G Trunc bP BSC with
Design an error correcting code for a BSC (BER=0.01) to achieve BER =0.00001 Step 1: indetifying the code parameters ( ) k ( ) ( ) ( ) 1 n n = = ' ' 1 1 1 1 1 , , n k P P P nP P P b b b b b b n=7, k=4
Homework assignment Design the coding scheme of a linear binary code with generator matrix 1 0 1 1 0 0 1 1 0 1 = G 2 5 x 1. Determine the codewords Give the parity check matrix H 2. 3. Determine the error groups (give the Standard Array of the code) 4. Determine the syndrome decoding table 5. Evaluate the probability of the error vectors occuring in the syndrome decoding table 6. Give the scheme of the system 7. Describe all the binary vectors in the scheme when sending all the possible message vectors (in each cases let the error vector have 1 in the first component and rest of the components are zeros).
Help for the homework 1 0 0 1 1 0 1 1 1 1 ( ) = = = (0) (0) c u G 00 1 0 0 1 1 0 1 1 1 1 ( ) = = = (1) (1) c u G 01 1 0 0 1 1 0 1 1 1 1 ( ) = = = (2) (2) c u G 10 1 0 0 1 1 0 1 1 1 1 ( ) 11 = = = (3) (3) c u G
Help for the homework ) 00001 = He s ; c are known ( T T = e Pick c (0) (1) (2) (3) c c ; ; ( ) ( ) ( ) ( ) E = s + + + (1) (2) (3) c c c 00001 ; 00001 ; 00001 ; 00001 ( ) e ( ) ( )( ) ( ) e n w e w = se e 1 P P P :min s e Ew s s b b s s e_s 000 001 010 011 100 101 110 111
Suggested readings D. Costello: Error control codes, Wiley, 2005, Chapter 3
Expected Quiz question 1. Given a generator matrix of a linear binary systematic code, determine the error group belonging to a given error vector 2. Give the parity check matrix of the C(15,11) Hamming code
