Unformatted text preview:

15-499: Algorithms and ApplicationsWhy Tornado Codes?The idea behind Tornado codesPowerPoint PresentationProperties of a good codeOutlineExpander GraphsExpander Graphs: ApplicationsExpander Graphs: PropertiesSlide 10Slide 11Slide 12Expander Graphs: ConstructionsSlide 14Slide 15Slide 16Slide 17Slide 18The loss modelTornado codes: EncodingTornado codes: DecodingSlide 22Slide 23What if check bits are lost?CascadingSlide 26Expander CodesExpander Codes: ConstructionSlide 29Slide 30Expander Graphs: Construction15-499 Page 115-499: Algorithms and ApplicationsError Correcting Codes – III - Expander graphs - Tornado codes - Expander codes15-499 Page 2Why Tornado Codes?•Desgined by Luby, Mitzenmacher, Shokrollahi et al•Forward Error Correction like RS & Linear codes•The other two give nearly optimal rates•But they are slow :Code Encoding DecodingLinear O(n2) O(n3)RS O(n log n) O(n2)Tornado O(n log 1/) O(n log 1/)15-499 Page 3The idea behind Tornado codes•Easy coding/decoding:linear codes with explicit construction•Fast coding/decoding:each check bit depends on only a few message bits15-499 Page 4Message bitsCheck bitsEach message bit is used in only a few check bitsThink of this as a “regular” Bipartite Graph => Low degree bipartite graphc6 = m3 © m715-499 Page 5Properties of a good code•There should be “few” check bits•Linear time encoding–Average degree on the left should be a small constant•Easy error detection/decoding–Each set of message bits should influence many check bits–Existence of unshared neighbors15-499 Page 6Outline•Expander Graphs–Applications–Properties–Constructions•Tornado Codes–Encoding/Decoding Algorithms–Brief Analysis•Expander Codes–Construction–Brief Analysis15-499 Page 7Expander Graphs•Expansion property: every small subset (k·n) has many neighbors (¸k)•Low degreek bits(k·n)k bits15-499 Page 8Expander Graphs: Applications•Pseudo-randomness (Derandomization)•Error Correcting Codes•Communication networks–Peer-to-peer networks–Gossip based protocols–Loss-resilient networks15-499 Page 9Expander Graphs: Properties•Expanders are “pseudo-random” objects•If we start at a node and wander around randomly, in a short while, we can reach any part of the graph•Expander-based codes behave like random linear codes, but have fast constructions.15-499 Page 10Expander Graphs: Properties•Expansion can be characterized using the eigenvaules of the graph•A = normalized adjacency matrix•Maximum eigenvalue is 1. (Why?)•Think of the eigenvectors as probability distributions•Second largest eigenvalue is an indicator of expansion – the smaller the better15-499 Page 11Expander Graphs: Properties•Prob. Dist. –  ; Uniform dist. – u•Small |-u| indicates a large amount of “randomness”•Show that |A-u| · 2|-u|•Therefore small 2 => fast convergence to uniform•Expansion  ¼ (1/2)215-499 Page 12Expander Graphs: Properties•To show that |A-u| · 2|-u|•Let  = u + ’•u is the principle eigenvector Au = u• ’ is perpendicular to u A’ · 2’•So, A · u + 2’•Thus, |A - u| · 2|’|15-499 Page 13Expander Graphs: Constructions•Important parameters – size, degree, expansion•Randomized constructions–A random d-regular graph is an expander with a high probability–Choose d random perfect matchings–Time consuming and cannot be stored compactly•Explicit constructions–Cayley graphs, Ramanujan graphs etc–Typical technique – start with a small expander, apply operations to increase its size15-499 Page 14Expander Graphs: Constructions•Start with a small expander, and apply operations to make it bigger while preserving expansion•Squaring–G2 contains edge (u,w) if G contains edges (u,v) and (v,w) for some node v–A’ = A2 – 1/d I– ’ = 2 – 1/d–d’ = d2 - dSize Degree Expansion 15-499 Page 15Expander Graphs: Constructions•Start with a small expander, and apply operations to make it bigger while preserving expansion•Tensor Product–G = AxB nodes are (a,b) 8 a2A and b2B–edge between (a,b) and (a’,b’) if A contains (a,a’) and B contains (b,b’)–n’ = n1n2– ’ = max (1, 2)–d’ = d1d2Size Degree Expansion 15-499 Page 16Expander Graphs: Constructions•Start with a small expander, and apply operations to make it bigger while preserving expansion•Zig-Zag product–“Multiply” a big graph with a small graphn2 = d1d2 = d115-499 Page 17Expander Graphs: Constructions•Start with a small expander, and apply operations to make it bigger while preserving expansion•Zig-Zag product–“Multiply” a big graph with a small graphSize Degree Expansion 15-499 Page 18OutlineExpander Graphs–Applications–Properties–Constructions•Tornado Codes–Encoding/Decoding Algorithms–Brief Analysis•Expander Codes–Construction–Brief Analysis15-499 Page 19The loss model•Random Erasure Model:Each bit is lost independently with some probability •We know the positions of the lost bits•Error Correction can be done with some more effort15-499 Page 20Tornado codes: Encoding•Why is it linear time?Computes the sum modulo 2 of its neighborsm1m2m3mnc1ck15-499 Page 21Tornado codes: Decoding•Assume that all the check bits are intact•Find a check bit such that only one of its neighbors is erasedm1m2m1+m2+c1 = m3mnc1ck15-499 Page 22Tornado codes: Decoding•Need to ensure that we can always find such a check bit•“Unshared neighbors” propertyConsider the set of corrupted message bit and their neighbors. Suppose this set is small.=> at least one message bit has an unshared neighbor.m1m2mnc1ckunshared neighbor15-499 Page 23Tornado codes: Decoding•Can we always find unshared neighbors?•Expander graphs give us this property•Also, [Luby et al] show that if we construct the graph from a specific kind of degree sequence, then we can always find unshared neighbors.15-499 Page 24What if check bits are lost?•Cascading–Use another bipartite graph to construct another level of check bits for the check bits–Final level is encoded using RS or some other coden n2nkn ¼ n15-499 Page 25Cascading•Total length of the code = n+n+2n+… · n/(1- )•Thus, rate is (1-)•Encoding time–for the first k stages : |E| = d x |V| = O(n)–for the last stage: n


View Full Document

CMU CS 15499 - Error Correcting Codes III

Documents in this Course
Load more
Download Error Correcting Codes III
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Error Correcting Codes III and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Error Correcting Codes III 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?