Method for optimizing the graph structure of codes based on Luby transformation

DOI: 10.31673/2412-9070.2025.042501

Abstract

The growing volume of information transmitted through communication channels leads to signifycant complications in data transmission conditions. This issue is typically caused by the presence of noise and various types of distortion. It is shown that error-resilient coding is crucial for ensuring the reliability of modern communication systems. Fountain codes are considered as an effective solution for data transmission in network environments with a high probability of packet loss. These codes are capable of adapting to different transmission conditions without the need for retransmission requests. The principles of encoding and decoding information using codes based on the Luby transformation are demonstrated, along with the advantages of such codes compared to traditional channel codes. The structure of Luby code graphs is presented, and the key problems and characteristics of their graph representation are discussed. It is established that the efficiency of the decoding process depends on the structure of the connection graph. Based on the conducted analysis, a method for optimizing the graph structure is proposed as a critical step toward enhancing performance. The main features and stages of the proposed optimization method for codes based on the Luby transfor mation are examined. A visual comparison and analysis of two graphs are provided—namely, the non-optimized Luby code graph and the graph after optimization. A comparative table with results before and after optimization is also presented. The obtained results show that optimizing the graph structure of Luby codes is a key factor in improving decoding speed and reliability, reducing the number of required additional symbols, ensuring effective coverage of input symbols, and minimizing data recovery errors. As a result of the study, it was determined that using the proposed method for graph structure optimization enables a reduction in computational complexity for Luby transform codes and allows them to operate more efficiently and reliably.

Keywords: fountain codes; Laby codes; bipartite graph; encoding; decoding; optimization; code symbols; data transmission; information; communication channel.