36:, but are much faster to generate and can fix erasures faster. Software-based implementations of tornado codes are about 100 times faster on small lengths and about 10,000 times faster on larger lengths than Reed–Solomon erasure codes. Since the introduction of Tornado codes, many other similar erasure codes have emerged, most notably
98:
if all the recovery blocks are present and the level beneath is missing at most C' fewer blocks than the recovery level. The algorithm for recovery is to find some recovery block that has only one of its generating set missing from the lower level. Then the xor of the recovery block with all of the
72:
All levels of recovery except the final one use an LDPC, which works by xor (exclusive-or). Xor operates on binary values, 1s and 0s. A xor B is 1 if A and B have different values and 0 if A and B have the same values. If you are given result of (A xor B) and A, you can determine the value for B.
107:
Tornado codes were formerly patented inside the United States of
America. Patents US6163870 A (filed Nov 6, 1997) and US 6081909 A (filed Nov 6, 1997) describe Tornado codes, and have expired as of November 6, 2017. Patents US6307487 B1 (filed Feb 5, 1999) and US6320520 B1 (filed Sep 17, 1999) also
87:
The final level is a Reed–Solomon code. Reed–Solomon codes are optimal in terms of recovering from failures, but slow to generate and recover. Since each level has fewer blocks than the one before, the Reed–Solomon code has a small number of recovery blocks to generate and to use in recovery. So,
68:
The number of recovery blocks is given by the user. Then the number of levels is determined along with the number of blocks in each level. The number in each level is determined by a factor B which is less than one. If there are N input blocks, the first recovery level has B*N blocks, the second
55:
error correction code, which is fast but has a chance of failure. The final layer uses a Reed–Solomon correction code, which is slower but is optimal in terms of failure recovery. Tornado codes dictates how many levels, how many recovery blocks in each level, and the distribution used to generate
64:
The input data is divided into blocks. Blocks are sequences of bits that are all the same size. Recovery data uses the same block size as the input data. The erasure of a block (input or recovery) is detected by some other means. (For example, a block from disk does not pass a CRC check or a
76:
So the recovery blocks in level one are just the xor of some set of input blocks. Similarly, the recovery blocks in level two are each the xor of some set of blocks in level one. The blocks used in the xor are chosen randomly, without repetition. However, the
73:(A xor B xor A = B) Similarly, if you are given result of (A xor B) and B, you can determine the value for A. This extends to multiple values, so given result of (A xor B xor C xor D) and any 3 of the values, the missing value can be recovered.
91:
During recovery, the Reed–Solomon code is recovered first. This is guaranteed to work if the number of missing blocks in the next-to-final level is less than the present blocks in the final level.
84:
Since xor is a fast operation and the recovery blocks are an xor of only a subset of the blocks in the input (or at a lower recovery level), the recovery blocks can be generated quickly.
289:
312:
209:. ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication. pp. 56–67.
205:
Byers JW, Luby M, Mitzenmacher M, Rege A (October 1998). "A digital fountain approach to reliable distribution of bulk data".
33:
52:
286:
307:
108:
mention
Tornado codes, and have expired as of February 5, 2019, and September 17, 2019, respectively.
81:
of blocks xor'ed to make a recovery block is chosen from a very specific distribution for each level.
268:
252:
228:
256:
232:
210:
29:
236:
32:. Tornado codes require a constant C more redundant blocks than the more data-efficient
94:
Going lower, the LDPC (xor) recovery level can be used to recover the level beneath it
293:
301:
17:
248:
224:
128:
116:
45:
37:
25:
133:
88:
even though Reed–Solomon is slow, it only has a small amount of data to handle.
241:
Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of
Computing
215:
51:
Tornado codes use a layered approach. All layers except the last use an
41:
261:
Proceedings of the 9th Annual ACM-SIAM Symposium on
Discrete Algorithms
259:(1998). "Analysis of Random Processes via And-Or Tree Evaluation".
176:
65:
network packet with a given sequence number never arrived.)
188:
152:
271:(2004). "Digital Fountains: A Survey and Look Forward".
99:
blocks that are present is equal to the missing block.
239:, Stemann V (1997). "Practical Loss-Resilient Codes".
273:Proc. 2004 IEEE Information Theory Workshop (ITW)
285:A readable description from CMU (PostScript)
69:has BĂ—BĂ—N, the third has BĂ—BĂ—BĂ—N, and so on.
8:
164:
214:
189:Luby, Mitzenmacher & Shokrollahi 1998
290:International Computer Science Institute
145:
7:
14:
56:blocks for the non-final layers.
1:
288:and another from Luby at the
119:created the Tornado codes.
329:
313:Capacity-approaching codes
34:Reed–Solomon erasure codes
207:SIGCOMM '98: Proceedings
216:10.1145/285237.285258
96:with high probability
165:Mitzenmacher 2004
153:Byers et al. 1998
320:
276:
264:
244:
220:
218:
192:
186:
180:
177:Luby et al. 1997
174:
168:
162:
156:
150:
30:error correction
328:
327:
323:
322:
321:
319:
318:
317:
298:
297:
283:
267:
247:
223:
204:
201:
196:
195:
187:
183:
175:
171:
163:
159:
151:
147:
142:
125:
114:
105:
62:
24:are a class of
12:
11:
5:
326:
324:
316:
315:
310:
300:
299:
282:
281:External links
279:
278:
277:
269:Mitzenmacher M
265:
253:Mitzenmacher M
245:
229:Mitzenmacher M
221:
200:
197:
194:
193:
181:
169:
157:
144:
143:
141:
138:
137:
136:
131:
124:
121:
113:
110:
104:
101:
61:
58:
13:
10:
9:
6:
4:
3:
2:
325:
314:
311:
309:
308:Coding theory
306:
305:
303:
296:
294:
292:(PostScript)
291:
287:
280:
274:
270:
266:
262:
258:
257:Shokrollahi A
254:
250:
246:
242:
238:
234:
233:Shokrollahi A
230:
226:
222:
217:
212:
208:
203:
202:
198:
190:
185:
182:
178:
173:
170:
166:
161:
158:
154:
149:
146:
139:
135:
132:
130:
127:
126:
122:
120:
118:
111:
109:
103:Patent issues
102:
100:
97:
92:
89:
85:
82:
80:
74:
70:
66:
59:
57:
54:
49:
47:
43:
39:
35:
31:
28:that support
27:
26:erasure codes
23:
22:Tornado codes
19:
18:coding theory
284:
272:
260:
240:
206:
184:
172:
160:
148:
129:Erasure code
117:Michael Luby
115:
106:
95:
93:
90:
86:
83:
78:
75:
71:
67:
63:
50:
46:Raptor codes
38:Online codes
21:
15:
134:Raptor code
302:Categories
263:: 364–373.
243:: 150–159.
237:Spielman D
199:References
112:Citations
123:See also
60:Overview
42:LT codes
249:Luby M
225:Luby M
79:number
140:Notes
53:LDPC
44:and
295:.
211:doi
16:In
304::
255:,
251:,
235:,
231:,
227:,
48:.
40:,
20:,
275:.
219:.
213::
191:.
179:.
167:.
155:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.