Understanding Error-Correcting Codes: Coding Theory and Applications
Delve into the world of error-correcting codes and frames with erasures, exploring how these algorithms help detect and correct errors in sequences of numbers. Discover the fundamentals of Coding Theory, the significance of reliable information transmission in noisy channels, and real-life applications in error detection and correction. Learn how techniques like doubling, tripling, and memory-efficient encoding improve error correction capabilities while minimizing memory usage.
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-Correcting Codes and Frames with Erasures Amanda S., Amy, Izzie, Katie SPWM July 30th, 2011
What it is An error-correcting code is an algorithm for expressing a sequence of numbers Any errors which are introduced can be detected and corrected (within certain limitations) based on the remaining numbers study of these codes known as Coding Theory
Coding Theory Transmits codes for reliable transmission of information across noisy channels Implores: Finite fields Group theory Polynomial algebra A branch of information theory
Error-Correcting and Compression Interested in: Detecting errors Correcting errors Examples where this is useful CD s Computer memory malfunction glitch
More Specifically Start with signal 1 0 1 1 0 1 0 0 1 1 0 Some corruption occurs 1 0 1 0 0 1 0 0 1 1 0 Impossible to know that it is not the original signal
Doubling the Bit Instead we double every bit 11 00 11 11 00 11 00 00 11 11 00 After corruption, bits are changed 11 01 11 11 00 11 00 00 10 11 00 Problem occurs with not knowing if 01 is supposed to be 00 or 11
Tripling the Bit Next we try tripling 111 000 111 111 000 111 000 000 111 111 000 After corruption, bits are changed 111 100 111 111 000 101 000 000 111 011 000 We can now detect and correct the error Unfortunately, memory needed has been tripled
Using Less Memory Original message: 1 0 1 1 0 1 0 0 1 1 0 Replace every two bit string with five bits 00 00001 01 01010 10 10100 11 11111 Apply to original message to get 10100 11111 01010 00001 11111
New String 10100 11111 01010 00001 11111 Memory increases by a factor of 2.5 rather than 3 2 code words are represented by a strand of 5 Can only correct single-flip errors
Change in Ideas Previously been discussing flipped bits, but now we will look at lost coefficients Applies to Equal-Norm Tight Frames Continuing to use the idea of perfectly reconstructing a signal despite corruption
Carrying Over to Equal-Norm Tight Frames Vectors can be written as elements in a frame and this representation may or may not be unique Frames are used in signal processing because: Resilience to additive noise Resilience to quantization Numerical stability of reconstruction Freedom to capture signal characteristics
The Purpose of Frames Information overflow at different nodes in the network Majority of loss due to unpredictable transport time If data is lost, retransmission requires more time and is not feasible Potential for large delay is unacceptable Because of independence between data, it is impossible to reconstruct what is lost
Equal-Norm Parseval Tight Frames (ENPTF) The ENPTF s are the frames that will be explored Minimizes mean-squared error if and only if it is tight To examine robust data transmission Robust resistance to the allowed number of erasures in a frame that is still frame Erasure missing coefficient in a frame
Mercedes-Benz Frame 1 0, 3 2 2 12 12 3 , Want this vector in the form: 12 3 12 3 1 0+ ?2 ? = ?1 + ?3 2 2 Say we want to send the vector ? =1 coefficients are computed as follows: 1. Then, the ?1=< ?,?1> = 1 1 2+ 3 3 1 2 ?2=< ?,?2> = 2= 1 2+ 3 1+ 3 2 ?3=< ?,?3> = = 2
Loss of Coefficient Once message is sent, the third coefficient is lost. We want to recover this using the first two coefficients: We define a new analysis operator to be: 1 0 3 ? = 12 2 We find the synthesis operator: 12 3 1 F = 0 2 We compute the frame operator: 3 54 3 4 S = F F = 34 4
We then found ?1 3 1 3 3 ? 1= 53 3 Then, using ? = ?=1 to reconstruct f to be: < ?,??>? 1(??), we are able 2 ? =1 1 This is the f that we had started with, so we were able to reconstruct our signal with the loss of a coefficient.
Another Example Another frame in 2is the Harmonic Tight Frame (HTF) 1 2 0 0 2 1 2 2 ? = 2 2 2 2 Note this frame can be formed by cos? 4 ?+1= , ? = 0,1,2,3 sin? 4
Robust to Erasures In an n-dimensional Hilbert Space, we want to find a frame that is robust to m-n erasures m is the number of vectors in the ENTPF We look specifically at being robust to one erasure.
Definition A frame ? is said to be robust to k ??=1 erasures if ? ? ?? is still a frame, for ? any index set of ? erasures, ? 1,2, ,? and ? = ?.
Proposition Let ? The following are equivalent: be a set of vectors in ?. ??=1 ??=1 is a frame robust to one ? 1. erasure. There are scalars ?? 0, for 1 ? ? so that ? 2. ?? ?= 0 ?=1
Proof ? (?): Choose ? 1,2, ,? maximal for which there are nonzero ?? s, ? ? and ? = ?? ?= 0 ? ? We claim that ? = ?. We proceed by contradiction. If ? {1,2, ,?}, choose ? ??. Since ? one erasure, there are scalars {??}, not all zero, so that ?is erased, it can be recovered from the rest as ??=1 is robust to ?= ?? ? ? ? or = ? ?? ? ?? ?= 0 ? ? ?? ? ?
Case 1 Assume that ??= 0 for all ? ?. Then, = ? ? ??? ? ? ? ?? ?? ?= 0. Recall our definition of ? = ? ??? ?= 0. We can write: ? + = ?? ?+ ? ?? ?= 0 + 0 = 0 ? ? ?? ? ? Therefore, ? + = 0 and has nonzero coefficients on every ?,? ?, plus a nonzero coefficient on ? contradicting the maximality of ?. Thus, our assumption that ??= 0 for all ? ? is false.
Case 2 At least one ?? 0 for some ? ?. By definition, ?? 0 for all ? ?, we can choose an ? > 0 so that ? ??, ?? for all ? ? ? + ? = ?? ?+ ?( ? ?? ? ?? ?) = 0 ? ? ?? ? ? ? ? Now, ? + ? = 0 and has nonzero coordinates on ?, for all ? ?, as well as ? for a coordinate on ?, again contradicting the maximality of ?. Thus, our assumption that at least one ?? 0 is false, so ?? 0 for all ? ?.
Proof Contd ? (?): Assume ?? 0, for all 1 ? ? and ?? ?= 0 ? ? Then for each ? ? we have: ?? ?? ?= ? ? ? ? That is, any vector lost can be recovered using the rest and so ? is robust to the erasure ?, for an arbitrary ? ?. ??=1
Works Cited Casazza, Peter G. and Jelena Kovacevic, Equal-Norm Tight Frames with Erasures. Adc. Comput. Math. 18, 287- 430. (2003). Daubechies, I. and S. Hughes. Error-Correcting and Compression Part 1: How come a scratched CD can still play flawlessly? . course notes, Math Alive, http://ww.math.princepton.edu/math_alive/2/Notes1.pdf. Weisstein, Eric W. "Coding Theory." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CodingTheory.html Weisstein, Eric W. "Error-Correcting Code." From MathWorld- -A Wolfram Web Resource. http://mathworld.wolfram.com/Error-CorrectingCode.html
