Understanding Linear Error Control Coding and Syndrome Detection in Binary Linear Codes

Delve into the world of linear error control coding, guided by Prof. Janos Levendovszky, as we explore the development of linear codes, message vectors, error groups, and the process of selecting group leaders with detailed examples. Discover how syndrome detection and decoding tables play a crucial role in identifying and correcting errors efficiently within binary linear codes.

• Linear Error Control Coding
• Syndrome Detection
• Binary Linear Codes
• Prof. Janos Levendovszky
• Coding Theory

mic_mcc Follow

Uploaded on Nov 27, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Error control coding binary linear codes Background material for linear error control codes Prof. Janos Levendovszky EU-USA Atlantis Programme FIT & BME

2. Developing linear codes C(5,2) 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 = = G H 2 5 x 3 5 x

3. Message vectors 1 0 0 1 1 0 1 1 1 1 ( ) ( ) = = = (0) (0) c u G 00 00000 1 0 0 1 1 0 1 1 1 1 ( ) ( ) = = = (1) (1) c u G 01 01111 1 0 0 1 1 0 1 1 1 1 ( ) ( ) = = = (2) (2) c u G 10 10110 1 0 0 1 1 0 1 1 1 1 ( ) 11 ( ) = = = (3) (3) c u G 11001

4. The error group for syndrome 001 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 = = G H 2 5 x 3 5 x 0 0 1 ( ) = = = = = = (1) (1) T T T s e He s e He 001 : : E E 1 001 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 ( ) = = = T e He 00001 ( ) ( ) ( ) ( ) = = = = = (1) (1) T T s e He s 001 : (00001), 01110 , 10111 , 11000 E E 1 001

5. Checking the error group property ( ) ( ) ( ) ( ) = = = = = (1) (1) T T s e He s 001 : (00001), 01110 , 10111 , 11000 E E 1 001 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 ( ) = = = T e He 00001 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 ( ) = = = T e He 01110

6. Selecting the group leader (P_b=0.01) ( ) ( ) ( ) ( ) = = = = = (1) (1) T T s e He s 001 : (00001), 01110 , 10111 , 11000 E E 1 001 w = w= w= w = 4 1 3 2 3 7 9 5 9,6*10 9,8*10 9,9*10 9,7*10 ( ) = The group leader is it occurs with the largest probability se 00001 ( ) = 001

7. The syndrome detection table Based on the syndrome vector we identify the correpsonding most likely error vector and we store these pairs in an LUT ! For example: Syndrome vector 000 001 010 011 100 101 110 111 Maximum likely error vector (the group leader) 00000 00001 00010 00011 00100 00101 10000 01000

8. Constructing the syndrome decoding table 0,...,2n 1 1. List the numbers in decimal from 2. Convert this decimal numbers to n bit binary numbers (the possible error vectors 0,1 e ) n n = e T T 3. Carry out the multiplications He s 0,1 4. Group the results with respect to s (collect all e vectors into the same group if they belong to the same s) 5. Determine the minimum weight e in each group 6. Construct an LUT by entering the s and the corresponding minimum weight e pairs

9. E.g.: constructing the syndrome decoding table of a C(5,2) code List of possible error vectors ( ( ( ( ) ) ) ) ( ) ( ( ) ) = e = e = e = e 0 1 00000 00001 13 01101 ( 01110 ( 01111 ( 10000 ( 10001 ( 10010 ( 10011 ( 10100 ( 10101 ( 10110 ( 10110 ( 11000 27 11011 ) = e = e 14 28 11100 = e 2 00010 ) ) ) ( ) = e = e 15 29 11101 = e 3 00011 ( 00100 00101 ( 00110 = e = e = = 16 17 18 19 ( ( ) ) = e 30 11110 ) = e = e = e 4 = e 31 11111 ( ) ) ) ) ) e e 5 6 = e 20 ( ) = e 7 00111 ) = e = 21 22 ( ) = e 8 01000 ) e ( ) = e 9 01001 ) = e 23 ( ) ) = e = e 10 01010 24 ( ( ) ) = e 25 11001 ( ) = e 11 01011 = e 26 11010 ( ) = e 12 01100

10. E.g.: constructing the syndrome decoding table of a C(5,2) code Multiplication with the generator matrix 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 = = = = = = T T T He He He 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 = = = = = = T T T He He He 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 1 = = = = = = T T T He He He

11. E.g.: constructing the syndrome decoding table of a C(5,2) code Multiplication with the generator matrix 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 = = T He = = = = T T He He 0 1 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 = = = = = = T T T He He He 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 1 = = = = = = T T T He He He

12. E.g.: constructing the syndrome decoding table of a C(5,2) code Multiplication with the generator matrix 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 = = T He = = = = T T He He 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 = = = = = = T T T He He He 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 = = = = = = T T T He He He

13. E.g.: constructing the syndrome decoding table of a C(5,2) code Multiplication with the generator matrix 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 = = T He = = = = T T He He 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 = = = = T T He He

14. Constructing the groups and assigning the group leaders = = e (00000),(01111),(10110),(11001) (00000) (000) E 000 = = e (00001),(01110),(10111),(11000) (00001) (001) E 001 = = e (00010),(01101),(10100),(11011) (00010) (010) E 010 = = e (00011),(01100),(10101),(11010) (00011) (011) E 011 = = 100 e (00100),(01011),(10010),(11101) (00100) (100) E = = 101 e (00101),(01010),(10011),(11100) (00101) (101) E = = 110 e (00110),(01001),(10000),(11111) (10000) (110) E = = 111 e (00111),(01000),(10001),(11110) (01000) (111) E

15. The syndrome decoding table Syndrome vector 000 001 010 011 100 101 110 111 Group leader error vector 00000 00001 00010 00011 00100 00101 10000 01000

16. Another way of constructing the error groups '= + e c e e E If and then e ' E s s 1. Pick an error vector e = T T He s 2. Calculate the corresponding syndrome vector 3. Construct the error group as follows ( ) k 2 E = s + + + (1) (2) e e c e c e c : , , ,..., e " E 4. Pick another error vector e for which and go back to Step 1. s

17. Example 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 ( ) = e Pick 00001 = = T He ( ) ( ) ( ) ( ) = = = = (0) (1) (2) (3) c c c c 00000 ; 01111 ; 10110 ; 11001 ( ) ( ) ( + ) ( ) ( + ) ( ) ( + ) = 00001 ; 00001 01111 ; 00001 10110 ; 00001 11001 E ( ) 001 ( ) ( ) ( ) ( ) = 00001 ; 01110 ; 10111 ; 11000 E ( ) 001 ( ) = e 00001 ( ) 001

18. Example (cont) 0 0 0 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 ( ) = e Pick 00010 = = T He ( ) ( ) ( ) ( ) = = = = (0) (1) (2) (3) c c c c 00000 ; 01111 ; 10110 ; 11001 ( ) ( ) ( + ) ( ) ( + ) ( ) ( + ) = 00010 ; 00010 01111 ; 00010 10110 ; 00010 11001 E ( ) 010 ( ) ( ) ( ) ( ) = 00010 ; 01101 ; 10100 ; 11011 E ( ) 001 ( ) = e 00010 ( ) 001

19. Example 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 ( ) = e Pick 00100 = = T He ( ) ( ) ( ) ( ) = = = = (0) (1) (2) (3) c c c c 00000 ; 01111 ; 10110 ; 11001 ( ) ( ) ( + ) ( ) ( + ) ( ) ( + ) = 00100 ; 00100 01111 ; 00100 10110 ; 00100 11001 E ( ) 100 ( ) ( ) ( ) ( ) = 00100 ; 01011 ; 10010 ; 11101 E ( ) 100 ( ) = e 00100 ( ) 100

20. Example 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 1 ( ) = e Pick 01000 = = T He ( ) ( ) ( ) ( ) = = = = (0) (1) (2) (3) c c c c 00000 ; 01111 ; 10110 ; 11001 ( ) ( ) ( + ) ( ) ( + ) ( ) ( + ) = 01000 ; 01000 01111 ; 01000 10110 ; 01000 11001 E ( ) 111 ( ) ( ) ( ) ( ) = 01000 ; 00111 ; 11110 ; 10001 E ( ) 111 ( ) = e 01000 ( ) 111

21. Example 1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 ( ) = e Pick 10000 = = T He ( ) ( ) ( ) ( ) = = = = (0) (1) (2) (3) c c c c 00000 ; 01111 ; 10110 ; 11001 ( ) ( ) ( + ) ( ) ( + ) ( ) ( + ) = 10000 ; 10000 01111 ; 10000 10110 ; 10000 11001 E ( ) 110 ( ) ( ) ( ) ( ) = 10000 ; 11111 ; 00110 ; 01001 E ( ) 110 ( ) = e 10000 ( ) 100

22. Example 0 0 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 0 1 ( ) = e Pick 00101 = = T He ( ) ( ) ( ) ( ) = = = = (0) (1) (2) (3) c c c c 00000 ; 01111 ; 10110 ; 11001 ( ) ( ) ( + ) ( ) ( + ) ( ) ( + ) = 00101 ; 00101 01111 ; 00101 10110 ; 00101 11001 E ( ) 101 ( ) ( ) ( ) ( ) = 00101 ; 01010 ; 10011 ; 11100 E ( ) 101 ( ) = e 00101 ( ) 001

23. Example 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 ( ) = e Pick 00011 = = T He ( ) ( ) ( ) ( ) = = = = (0) (1) (2) (3) c c c c 00000 ; 01111 ; 10110 ; 11001 ( ) ( ) ( + ) ( ) ( + ) ( ) ( + ) = 00011 ; 00011 01111 ; 00011 10110 ; 00011 11001 E ( ) 011 ( ) ( ) ( ) ( ) = 00011 ; 01100 ; 10101 ; 11010 E ( ) 011 ( ) = e 00011 ( ) 011

24. The syndrome decoding table Syndrome vector 000 001 010 011 100 101 110 111 Group leader error vector 00000 00001 00010 00011 00100 00101 10000 01000

25. 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

26. The coding scheme ( ) P e=(10111) ( )= 10-2 40.99 = 9.9*10-9 s e 000 00000 10111 001 00001 001 11000 11001 01111 11 00001 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

27. The standard array Syndrome vector 000 001 010 011 100 101 110 111 0 1 2 3 00000 00001 00010 00011 00100 00101 00110 00111 01111 01110 01101 01100 01011 01010 01001 01000 10110 10111 10100 10101 10010 10011 10000 10001 11001 11000 11011 11010 11101 11100 11111 11110