Error control coding techniques

Presentation on error control coding techniques

1. ERROR CONTROL CODING TECHNIQUES BY : DHANASHRI NANDRE 202081011 VJTI-ELECTRICAL DEPT. ELECTRONICS BRANCH- PRESENTATION FOR ACT ‹#›

2. CONTENTS : Introduction & Explanation - Need of error correcting codes. - Cyclic Codes - LDPC Codes Literature Survey Significance of previous research Performance Comparison Recommendation Future Scope Conclusion References ‹#›

3. What is error ? The input data can’t be the same as the output data.This mismatch is known as “Error” Result in the loss of important or secure data Types[1] - 1.Single Bit Errors 2.Multi Bit Errors 3.Burst Errors ‹#›

4. What is Need Of Error Correcting Codes Requirements of communication systems are stringent Reliability in communication increases Cause of Error [1] - Echo,crosstalk,impulsive noise,thermal noise ‹#›

5. What is error Detection And Correction ? Error Detection - Detecting the errors which are present in the data transmitted from transmitter to receiver[1] Types of error detection- Parity Checking Cyclic Redundancy Check (CRC) Longitudinal Redundancy Check (LRC) Repetition codes ‹#›

6. What is error Detection And Correction ? Error Correction - After detecting the errors reconstructing the original error-free data Ensures that corrected and error-free messages are obtained at the receiver side Types of error detection[1]- Automatic repeat request (ARQ) Forward error correction Hybrid schemes ‹#›

7. ‹#› Cyclic Codes

8. Cyclic Code Cyclic code is a linear code A linear [n,k] code C over a finite field GF(q) is called cyclic if (C0,C1,..Cn-1) ∈ C implies (Cn-1,C0,C1…..Cn-2) ∈ C [2] The error correcting capability of cyclic codes may not be as good as some other linear codes in general [2] Cyclic codes have wide applications in storage and communication systems because they have efficient encoding and decoding algorithms [2] Ways to encode & Decode the cyclic code - 1- Polynomials Method 2- Shift Register Method ‹#›

9. Encoding of message by Cyclic Codes Encoding process contains following steps: [3] Step 1 - Multiply u(x) by x^(n−k) Step 2 - Divide x^(n−k).u(x) by g(x) Step 3 - Form the code word b(x) + x^(n−k).u(x) ‹#›

10. ‹#› Remainder = parity bit Eg-Generator polynomial for (7,4) is given by X^3+X+1. Determine the code vector in systematic form for sequence 1011

11. ‹#›

12. ‹#›

13. ‹#›

14. ‹#› Shift Register Method [3]

15. ‹#›

16. De coding of message by Cyclic Codes De coding process contains following steps: Step 1 - Syndrome computation Step 2 - Association of the syndrome to an error pattern Step 3 - Error correction ‹#›

17. Syndrome Decoding Syndrome polynomial to be the remainder of. division by generator polynomial: s(x) = r(x) mod g(x) = s0 + s1x + ··· + sn-k-1xn-k-1. Every codeword is a multiple of g(x), so codewords have syndrome 0 Example - For a (7,4) code dimension the g(x)=X^3+X+1 and received sequence is R = 1001000. Find the sequence is valid or not & Correct it ‹#›

18. ‹#›

19. ‹#›

20. ‹#›

21. ‹#› A rate k = 2 network G with source node s and sink nodes t1 and t2, and the associated network G′ constructed using Algorithm. [4]

22. ‹#› Algorithm 1 1 [4] Layer 0 contains only a source node denoted s0. A node denoted v1,e is associated with each edge e ∈ E \Out(s), and layer 1 consists of only these nodes. The node v1,e is connected to s0 by an edge denoted e(1) Layer 2 consists of nodes denoted v2,e where e ∈ E, and v2,e corresponds to edge e ∈ E. For any edge e ∈ E\Out(s), the vertices v1,e and v2,e are connected by an edge denoted by e(2). In addition, for any length 2 directed path e′e in G, the vertices v1,e and v2,e′ are connected by an edge denoted e′e Similar to layer 2, the set of vertices in layer 3 consists of nodes {v3,e}e∈E, and for each edge e ∈ E vertices v2,e and v3,e are connected by an edge denoted e(3) Corresponding to any node v in G that is either the source node s or a sink node ti, a node v4,s or v4,ti is considered and these nodes form layer 4.

23. Applications of Cyclic Codes In DNA Codes (A-G-T-C) [5] In Steganography [6] ‹#›

24. ‹#› LDPC Codes

25. Introduction Low-density parity-check [7] Originally invented and investigated by Gallager in 1960 [7] High SNR High Data Rate N bit long LDPC code in terms of M no. of Parity Check equations and describing those Parity Checks with a M * N Parity Check Matrix H. [7] M - No. of parity check equations N - No. of bits in the codeword ‹#›

26. ‹#› At receiver message bit can be easily decoded by comparing two copies bit by bit Speed of communication is high But unfortunately this process of repetition gets fails whenever same bit is missing

27. ‹#› Decoder fails to completely decode the message bit Biggest challenge for the communication engineers Also it doubles the message length no matter what is the number of erasers This efficiency issue can be expressed by CODE RATE

28. ‹#› Lower code is a more expensive to design Every bit we transmit has some cost So there is a balance to strike between the code rate and the probability of failure We need a coding strategy with just enough protection bits to prevent failure & For that purpose LDPC codes arrives

29. ‹#› (a) (b) (c) (d)

30. ‹#› Overlapping approach extended Process of decoding parity check bits goes very much complex Slow down the communication process

31. ‹#› What we need is - Code with very fast decode operations [7] We left with final problem How can we extend this overlapping subset approach to work quickly over very long message [7]

32. Representations of LDPC code An [ n , k , d ] LDPC code may be represented by a Tanner graph G ( V , E ) The parity-check matrix H of the LDPC code consists of rows and Columns T he set of vertices Vv(G) and Vp(G) are called variable and parity-check vertices, respectively ‹#›

33. Representations of a [16, 4, 4] LDPC code [11] ‹#›

34. Algorithms Encoder [8] L abel-and-decide Method Pseudo Tree Triangular Factorisation Tanner Graph Method Decoder Bit Flip Algorithm Long Domain Based Sum product Algorithm Probability Domain Based Sum product Algorithm ‹#›

35. ‹#› Flow-chart for LDPC matrix creation

36. ‹#› Start M : rows N: columns onePerCol:no of 1’s Iter : no.of iterations Ensures rows & columns have same number of 1’s 1’s added to rows that have single 1 or have none of them End

37. ‹#›

38. ‹#›

39. ‹#›

40. ‹#› Lets see the difference of LDPC Coded and uncoded Codeword[10] https://matlab.mathworks.com/

41. Application of LDPC Codes In storage devices In communication devices ‹#›

42. ‹#› Sr. No. Title of paper P ublication & Author Summary 01 Error Correction Technique Based On Forward Error Correction For H.264 Codec 2012 IEEE J.A.S.N.Jayasooriya, Y.L.Midipolawatta, M.B.Dissanayake An efficient error correction algorithm is proposed to improve the reconstructed video quality in an error-prone network 02 On Capacity of Network Error Correction Coding with Random Errors 2018 IEEE letter Wangmei Guo, Dan He and Ning Cai Non-linear coding at the source and linear coding at intermediate nodes over the general multicast network, which is proved to be able to achieve strictly higher transmission rate than linear NEC 03 Single-Error Detection and Correction for Duplication and Substitution Channels 2020 IEEE Yuanyuan Tang, Yonatan Yehezkeally, Student Member, IEEE, Moshe Schwartz, Senior Member, IEEE, and Farzad Farnoud, Member, IEEE They focused on two noise models, where the substitution error is either restricted to occur in an inserted copy during one of the duplication events, or may occur at any position in the string Literature survey

43. ‹#› Sr. No. Title of paper Publication & Author Summary 04 Efficient Decoding of Short Length Linear Cyclic Codes IEEE COMMUNICATIONS LETTERS, VOL. 19, NO. 4, APRIL 2015 A number of iterative decoding algorithms have been proposed in the literature for the decoding of linear block codes.The technique proposed in this paper also utilises the BP algorithm with the key difference of incorporating the permutation into the message passing process 04 Construction of MDS Convolutional Error-correcting Network Codes Over Cyclic Networks I EEE Transactions on Communications ( Volume: 65, Issue: 6, June 2017) In this paper, a construction algorithm was presented for ring-based MDS linear network codes over cyclic networks. This algorithm was first developed for acyclic networks, and then network de-cycling was used to extend it to general cyclic networks. Finally, the complexity of the proposed algorithm was analyzed 05 Cyclic Low Density Parity Check Codes With the Optimum Burst Error Correcting Capability Received October 2, 2020, accepted October 15, 2020, date of publication October 21, 2020, date of current version November 2, 2020. The paper presents a new scheme of cyclic codes suitable for the correction of burst errors.y. Considering the parity check matrix of these codes, bounds for determining their burst error correction were presented

44. ‹#› Sr. No. Title of paper Publication & Author Summary 07 Error-Prediction LDPC and Error-Recovery Schemes for Highly Reliable Solid-State Drives (SSDs) IEEE Journal of Solid-State Circuits Year: 2013 The whole system in this paper was constructed of a PC and the SSD system. If they are implemented in ASIC, the gate count of the EP-LDPC codec in the NAND controller is similar to the conventional LDPC 08 New Decoding Scheme for LDPC Codes Based on Simple Product Code Structure JOURNAL OF COMMUNICATIONS AND NETWORKS, VOL. 17, NO. 4, AUGUST 2015 The proposed decoding scheme adopts a simple product code structure to have a strong post-processing for good error correcting performance of LDPC codes. It mainly takes advantage of combining two independently received soft-decision data for the same codeword. 05 On Efficient Concatenation of LDPC Codes With Constrained Codes © 2015 IEEE. Publication Chi Dinh Nguyen1,2,3, Kui Cai1 , Bingrui Wang1 , and Yan Hong1 In t he paper they proposed two new methods for concatenating the LDPC codes with the constrained codes. The proposed designs deployed the nibble-based technique to generate k constrained sequences. I

45. Performance comparison ‹#›

46. Future scope Interesting area of future research is the study of how the presence of caches would affect the correlation in the data input to the ECC memory, and whether there is any systematic pattern there that can be exploited by the optimization algorithms Furthermore we can make it possible to implement parallelizable decoders. ‹#›

47. Conclusion To conclude this presentation I can say that error codes have been developed to specifically protect against both random bit errors and burst errors. Real-time systems must consider tradeoffs between coding delay and error protection. To conclude second part of the presentation I Also can say that the cyclic codes have a very good performance in detecting single-bit errors, double errors, an odd number of errors, and burst errors & LDPC code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. ‹#›

48. References [1] J.A.S.N.Jayasooriya, Y.L.Midipolawatta, M.B.Dissanayake,”Error Correction Technique Based On Forward Error Correction For H.264 Codec”(2012) [2]Shuhei Tanakamaru,Yuki Yanagihara, Ken Takeuchi,”Error-Prediction LDPC and Error-Recovery Schemes for Highly Reliable Solid-State Drives(SSDs) “(2013) [3]Mohamed Ismail, Stojan Denic, and Justin Coon,”Efficient Decoding of Short Length Linear Cyclic Codes”(2015) [4]Beomkyu Shin,Seokbeom Hong,Hosung Park,Jong-SeonNo,andDong-JoonShin,”New Decoding Scheme for LDPC Codes Based on Simple Product Code Structure”(2015) [5]Chi Dinh Nguyen1,2,3, Kui Cai1, Bingrui Wang1, and Yan Hong1,”On Efficient Concatenation of LDPC Codes with Constrained Codes “(2015) [6]Vahid SAMADI-KHAFTARI1, Morteza ESMAEILI1,2, Thomas Aaron GULLIVER2, ”Construction of MDS Convolutional Error-correcting Network Codes Over Cyclic Networks”(2017) [7]Wangmei Guo, Dan He and Ning Cai,”On Capacity of Network Error Correction Coding with Random Errors “(2018) [8]Yuanyuan Tang, Yonatan Yehezkeally,”Single-Error Detection and Correction for Duplication and Substitution Channels”(2020) [9]SINA VAFI ,”Cyclic Low Density Parity Check Codes With the Optimum Burst Error Correcting Capability”(2020) “ ‹#›