Search

This paper investigates the construction of random-structure LDPC (low-density parity-check) codes using Progressive Edge-Growth (PEG) algorithm and two proposed algorithms for removing short cycles (CB1 and CB2 algorithm; CB stands for Cycle Break). Progressive Edge-Growth is an algorithm for computer-based design of random-structure LDPC codes, the role of which is to generate a Tanner graph (a bipartite graph, which represents a parity-check matrix of an error-correcting channel code) with as few short cycles as possible. Short cycles, especially the shortest ones with a length of 4 edges, in Tanner graphs of LDPC codes can degrade the performance of their decoding algorithm, because after certain number of decoding iterations, the information sent through its edges is no longer independent. The main contribution of this paper is the unique approach to the process of removing short cycles in the form of CB2 algorithm, which erases edges from the code's parity-check matrix without decreasing the minimum Hamming distance of the code. The two cycle-removing algorithms can be used to improve the error-correcting performance of PEG-generated (or any other) LDPC codes and achieved results are provided. All these algorithms were used to create a PEG LDPC code which rivals the best-known PEG-generated LDPC code with similar parameters provided by one of the founders of LDPC codes. The methods for generating the mentioned error-correcting codes are described along with simulations which compare the error-correcting performance of the original codes generated by the PEG algorithm, the PEG codes processed by either CB1 or CB2 algorithm and also external PEG code published by one of the founders of LDPC codes, В данной статье исследуется построение LDPC-кодов (с малой плотностью проверок на чётность) со случайной структурой с использованием алгоритма прогрессивного роста ребер (PEG) и двух предложенных алгоритмов удаления коротких циклов (алгоритм CB1 и CB2; CB означает Cycle Break (Разрыв циклов)). Progressive Edge-Growth (Прогрессивный рост ребер) – это алгоритм компьютерного проектирования LDPC-кодов со случайной структурой, который заключается в создании графа Таннера (двудольного графа, представляющего матрицу проверки на четность корректирующего кода канала) с как можно меньшим количеством коротких циклов. Короткие циклы, особенно самые короткие с длиной 4 ребра, в графах Таннера LDPC-кодов способны ухудшить производительность алгоритма декодирования, поскольку после определенного числа итераций декодирования информация, передаваемая через его ребра, перестает быть независимой. Основным вкладом статьи является уникальный подход к процессу удаления коротких циклов в виде алгоритма CB2, который удаляет ребра из матрицы проверки на четность кода без уменьшения минимального расстояния Хэмминга кода. Два алгоритма удаления циклов могут быть использованы для улучшения корректирующей эффективности PEG-генерируемых (или любых других) LDPC-кодов, представляются достигнутые результаты. Все эти алгоритмы были использованы для создания PEG LDPC-кода, который конкурирует с наиболее известным PEG-генерируемым LDPC-кодом с аналогичными параметрами, предоставленным одним из основателей LDPC-кодов. Описаны методы генерации упомянутых корректирующих кодов, а также моделирование, в котором сравнивается корректирующая эффективность исходных кодов, сгенерированных алгоритмом PEG, PEG-кодов, обработанных алгоритмом CB1 или CB2, а также внешнего PEG-кода, опубликованного одним из основателей LDPC-кодов, У даній статті досліджується побудова LDPC-кодів (з малою щільністю перевірок на парність) з випадковою структурою з використанням алгоритму прогресивного зростання ребер (PEG) і двох запропонованих алгоритмів видалення коротких циклів (алгоритм CB1 і CB2; CB означає Cycle Break (Розрив циклів)). Progressive Edge-Growth (Прогресивне зростання ребер) – це алгоритм комп'ютерного проектування LDPC-кодів з випадковою структурою, який полягає у створенні графа Таннера (дводольного графа, що представляє матрицю перевірки на парність коригуючого коду каналу) з якомога меншою кількістю коротких циклів. Короткі цикли, особливо найкоротші з довжиною 4 ребра, в графах Таннера LDPC-кодів здатні погіршити продуктивність алгоритму декодування, оскільки після певного числа ітерацій декодування інформація, передана через його ребра, перестає бути незалежною. Основним внеском статті є унікальний підхід до процесу видалення коротких циклів у вигляді алгоритму CB2, який видаляє ребра з матриці перевірки на парність коду без зменшення мінімальної відстані Хеммінга коду. Два алгоритми видалення циклів можуть бути використані для поліпшення коригуючої ефективності PEG-генерованих (або будь-яких інших) LDPC-кодів, представляються досягнуті результати. Всі ці алгоритми були використані для створення PEG LDPC-коду, який конкурує з найбільш відомим PEG-генерованим LDPC-кодом з аналогічними параметрами, наданим одним із засновників LDPC-кодів. Описані методи генерації згаданих коригуючих кодів, а також моделювання, в якому порівнюється коригуюча ефективність вихідних кодів, згенерованих алгоритмом PEG, PEG-кодів, оброблених алгоритмом CB1 або CB2, а також зовнішнього PEG-коду, опублікованого одним із засновників LDPC-кодів.