471:
225:
In TNC, coding is performed in two stages. First redundant "0" bits are added at the head and tail of each packet such that all packets are of uniform bit length. Then the packets are
174:
338:
278:
121:
85:
298:
240:. However, since the packets in TNC have been coded in such a manner that the resulting coded packets are in triangular pattern, the computational process of
189:
512:
221: + 3 bits. Information about the number of redundant '0' bits added at the head of each packet is included in the coded packet's header.
392:
357:
Qureshi, Jalaluddin; Foh, Chuan Heng; Cai, Jianfei (2012). "Optimal solution for the index coding problem using network coding over GF(2)".
48:
alleviates the concern of high computational complexity, coding over GF(2) comes at the tradeoff cost of degrading throughput performance.
546:
36:. Previously, packet coding for network coding was done using linear network coding (LNC). The drawback of LNC over large
127:
is the total number of data packets being encoded in a coded packet) without degrading the throughput performance, with
541:
505:
359:
2012 9th Annual IEEE Communications
Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON)
51:
The main contribution of triangular network coding is to reduce the worst-case decoding computational complexity of
229:, bit-by-bit. The "0" bits are added in such a way that these redundant "0" bits added to each packet generate a
536:
531:
498:
455:
J. B. Fraleigh, and R. A. Beauregard, Linear
Algebra. Chapter 10, Addison-Wesley Publishing Company, 1995.
372:
237:
188:
177:
478:
398:
362:
141:
388:
307:
247:
230:
176:. It has been further shown that triangular based fountain code can even outperform optimized
90:
54:
433:
380:
138:
to achieve near-optimal performance with encoding and decoding computational complexity of
376:
482:
283:
41:
29:
525:
135:
17:
470:
402:
226:
37:
300:
is the number of packets, can be bypassed. The receiver now only needs to perform
438:
421:
384:
236:
In essence, the TNC decoding process, like the LNC decoding process involves
128:
367:
45:
422:"Triangular code: Near-optimal linear time fountain code"
486:
310:
286:
250:
144:
93:
57:
420:
Qureshi, Jalaluddin; Foh, Chuan Heng (August 2023).
332:
292:
272:
168:
115:
79:
40:is that it resulted in high encoding and decoding
415:
413:
192:An example of coding four packets using TNC. Bit
131:comparable to that of optimal coding schemes.
506:
33:
8:
451:
449:
217:bits. The resulting coded packet has length
213:packet. Each packet has original length of
513:
499:
134:Triangular code has also been proposed as
44:. While linear encoding and decoding over
437:
366:
321:
309:
285:
261:
249:
143:
104:
92:
68:
56:
32:based packet coding scheme introduced by
187:
349:
7:
467:
465:
304:with worst-case complexity given as
426:Digital Communications and Networks
14:
469:
327:
314:
267:
254:
163:
148:
110:
97:
74:
61:
1:
34:Qureshi, Foh & Cai (2012)
485:. You can help Knowledge by
563:
464:
439:10.1016/j.dcan.2022.12.006
385:10.1109/SECON.2012.6275780
169:{\displaystyle O(n\log n)}
22:triangular network coding
547:Telecommunications stubs
477:This article related to
333:{\displaystyle O(n^{2})}
273:{\displaystyle O(n^{3})}
116:{\displaystyle O(n^{2})}
80:{\displaystyle O(n^{3})}
42:computational complexity
340:for each bit location.
334:
294:
274:
222:
170:
117:
81:
335:
295:
275:
205:∈ {0,1} is the
191:
171:
118:
82:
361:. pp. 134–142.
308:
284:
248:
238:Gaussian elimination
142:
91:
55:
377:2012arXiv1209.6539Q
244:with complexity of
184:Coding and decoding
178:Luby transform code
542:Information theory
479:telecommunications
330:
302:back-substitution,
290:
270:
242:triangularization,
231:triangular pattern
223:
166:
113:
77:
28:) is a non-linear
494:
493:
394:978-1-4673-1905-8
293:{\displaystyle n}
554:
515:
508:
501:
473:
466:
456:
453:
444:
443:
441:
417:
408:
406:
370:
354:
339:
337:
336:
331:
326:
325:
299:
297:
296:
291:
279:
277:
276:
271:
266:
265:
175:
173:
172:
167:
122:
120:
119:
114:
109:
108:
86:
84:
83:
78:
73:
72:
562:
561:
557:
556:
555:
553:
552:
551:
522:
521:
520:
519:
462:
460:
459:
454:
447:
419:
418:
411:
395:
356:
355:
351:
346:
317:
306:
305:
282:
281:
257:
246:
245:
204:
186:
140:
139:
100:
89:
88:
64:
53:
52:
12:
11:
5:
560:
558:
550:
549:
544:
539:
534:
524:
523:
518:
517:
510:
503:
495:
492:
491:
474:
458:
457:
445:
432:(4): 869–878.
409:
393:
348:
347:
345:
342:
329:
324:
320:
316:
313:
289:
269:
264:
260:
256:
253:
196:
185:
182:
165:
162:
159:
156:
153:
150:
147:
112:
107:
103:
99:
96:
76:
71:
67:
63:
60:
30:network coding
13:
10:
9:
6:
4:
3:
2:
559:
548:
545:
543:
540:
538:
537:Finite fields
535:
533:
532:Coding theory
530:
529:
527:
516:
511:
509:
504:
502:
497:
496:
490:
488:
484:
480:
475:
472:
468:
463:
452:
450:
446:
440:
435:
431:
427:
423:
416:
414:
410:
404:
400:
396:
390:
386:
382:
378:
374:
369:
364:
360:
353:
350:
343:
341:
322:
318:
311:
303:
287:
262:
258:
251:
243:
239:
234:
232:
228:
220:
216:
212:
208:
203:
199:
195:
190:
183:
181:
179:
160:
157:
154:
151:
145:
137:
136:Fountain code
132:
130:
126:
105:
101:
94:
69:
65:
58:
49:
47:
43:
39:
35:
31:
27:
23:
19:
18:coding theory
487:expanding it
476:
461:
429:
425:
358:
352:
301:
241:
235:
224:
218:
214:
210:
206:
201:
197:
193:
133:
124:
50:
38:finite field
25:
21:
15:
209:bit of the
526:Categories
344:References
368:1209.6539
227:XOR coded
158:
129:code rate
280:, where
403:8977891
373:Bibcode
123:(where
401:
391:
481:is a
399:S2CID
363:arXiv
46:GF(2)
483:stub
389:ISBN
434:doi
381:doi
155:log
87:to
26:TNC
16:In
528::
448:^
428:.
424:.
412:^
397:.
387:.
379:.
371:.
233:.
180:.
20:,
514:e
507:t
500:v
489:.
442:.
436::
430:9
407:.
405:.
383::
375::
365::
328:)
323:2
319:n
315:(
312:O
288:n
268:)
263:3
259:n
255:(
252:O
219:B
215:B
211:k
207:i
202:k
200:,
198:i
194:b
164:)
161:n
152:n
149:(
146:O
125:n
111:)
106:2
102:n
98:(
95:O
75:)
70:3
66:n
62:(
59:O
24:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
