Triangular code: Near-optimal linear time fountain code

Jalaluddin Qureshi

doi:10.1016/j.dcan.2022.12.006

Return

Triangular code: Near-optimal linear time fountain code

2023-08-01

Jalaluddin Qureshi *

Chuan Heng Foh

DOI：10.1016/j.dcan.2022.12.006

Original

Save

View PDF

Abstract

En 中文

In this paper, we propose Triangular Code (TC), a new class of fountain code with near-zero redundancy and linear encoding and decoding computational complexities of OoLklog k thorn , where k is the packet batch size and L is the packet data length. Different from previous works where the optimal performance of codes has been shown under asymptotic assumption, TC enjoys near-zero redundancy even under non-asymptotic settings for small-moderate number of packets. These features make TC suitable for practical implementation in battery-constrained devices in IoT, D2D and M2M network paradigms to achieve scalable reliability, and minimize la-tency due to its low decoding delay. TC is a non-linear code, which is encoded using the simple shift and XOR addition operations, and decoded using the simple back-substitution algorithm. Although it is nonlinear code at the packet level, it remains linear code when atomized at the bit level. We use this property to show that the back-substitution decoder of TC is equivalent to the Belief Propagation (BP) decoder of LT code. Therefore, TC can benefit from rich prolific literature published on LT code, to design efficient code for various applications. Despite the equivalency between the decoders of TC and LT code, we show that compared to state-of-the-art optimized LT code, TC reduces the redundancy of LT code by 68%-99% for k reaching 1024.& COPY; 2022 Published by Elsevier Ltd.

Keywords:

LT code

Decoder

Computational complexity

Green computing

Network coding

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.