РАЗРАБОТКА ВЫСОКОПРОИЗВОДИТЕЛЬНОГО ДЕКОДЕРА КОДА РИДА–СОЛОМОНА RS(544,514) С ИСПОЛЬЗОВАНИЕМ NUMPY НА ЯЗЫКЕ PYTHON

АННОТАЦИЯ

В статье рассматривается реализация декодера кода Рида–Соломона RS(544,514) с применением векторизованных вычислений на основе библиотеки NumPy. Приведено описание основных этапов алгоритма декодирования. Предложенный подход позволяет существенно ускорить основные этапы декодирования, включая вычисление синдромов, поиск позиций ошибок и их исправление. Проведён анализ вычислительной сложности и показано, что использование векторизации вычислений и оптимизация операций в конечном поле GF(2¹⁰) обеспечивает ускорение до 30 раз по сравнению с классической реализацией на Python. Полученные результаты подтверждают эффективность применения векторизации для повышения производительности алгоритмов коррекции ошибок.

ABSTRACT

The article discusses the implementation of the Reed–Solomon RS(544.514) code decoder using vectorized calculations based on the NumPy library. The main stages of the decoding algorithm are described. The proposed approach makes it possible to significantly speed up the main stages of decoding, including the calculation of syndromes, the search for error positions and their correction. An analysis of computational complexity is carried out and it is shown that the use of vectorization of calculations and optimization of operations in the finite field GF(210) provides acceleration up to 30 times compared with the classical Python implementation. The results obtained confirm the effectiveness of using vectorization to improve the performance of error correction algorithms.

Ключевые слова: Коды Рида–Соломона, декодирование, NumPy, конечные поля, Берлекэмп–Мэсси, поиск Ченя.

Keywords: Reed–Solomon codes, decoding, NumPy, finite fields, Berlekamp–Massey, Chien search.

Введение

Коды Рида–Соломона являются одним из наиболее эффективных средств коррекции ошибок в цифровых системах передачи и хранения данных. Они широко применяются в телекоммуникациях, оптических каналах связи и системах хранения информации [1].

С развитием высокоскоростных систем возникает необходимость в эффективной программной реализации декодеров. Традиционные реализации на Python обладают низкой производительностью, что ограничивает их применение. В связи с этим актуальной задачей является разработка оптимизированных алгоритмов декодирования.

Целью данной работы является создание высокопроизводительного декодера RS(544,514) с использованием векторизации вычислений.

Материалы и методы исследования

Рассматриваемый код характеризуется параметрами:

• длина кодового слова: 𝑛=544 [2];
• длина информационной части: 𝑘=514 [2];
• корректирующая способность:

Код строится над конечным полем Галуа GF(2¹⁰) [3].

Полученное слово описывается выражением:

R(x)=C(x)+E(x),

где E(x) – многочлен ошибок [3].

Процесс декодирования включает следующие этапы:

• Вычисление синдромов;
• Определение многочлена локаторов ошибок (алгоритм Берлекэмпа–Мэсси) [4; 5];
• Поиск позиций ошибок (алгоритм Ченя);
• Вычисление величин ошибок (формула Форни);
• Исправление ошибок.

Для ускорения вычислений используются таблицы логарифмов и анти-логарифмов, представленные в виде массивов NumPy:

import numpy as np

class GF:

    def __init__(self, m=10, prim=0b10000001001):

        self.m = m

        self.prim = prim

        self.size = 1 << m

        self.exp = np.zeros(2 * self.size, dtype=np.int32)

        self.log = np.zeros(self.size, dtype=np.int32)

        self._init_tables()

Такой подход позволяет заменить операции умножения и деления на операции индексации массивов.

Синдромы вычисляются векторно на приведенном ниже листинге:

 def compute_syndromes(received, gf, t):

    received = np.array(received, dtype=np.int32)

    n = len(received)

    j = np.arange(n)

    syndromes = []

    for i in range(1, 2*t + 1):

        powers = gf.exp[(i * j) % (gf.size - 1)]

        terms = received ^ powers

        syndromes.append(np.bitwise_xor.reduce(terms))

    return np.array(syndromes)

Векторизация позволяет устранить вложенные циклы и существенно ускорить вычисления.

Реализация алгоритма использует частичную векторизацию:

def berlekamp_massey(syndromes, gf):

    C = np.zeros(len(syndromes)+1, dtype=np.int32)

    B = np.zeros(len(syndromes)+1, dtype=np.int32)

    C[0] = 1

    B[0] = 1

Данный алгоритм определяет многочлен локаторов ошибок.

Наиболее значительное ускорение достигается на этапе поиска ошибок:

def chien_search(locator, n, gf):

    i = np.arange(n)

    val = np.zeros(n, dtype=np.int32)

    for j in range(len(locator)):

        if locator[j] != 0:

            val ^= gf.exp[(gf.log[locator[j]] + j * i) % (gf.size - 1)]

    return np.where(val == 0)[0]

Этот этап полностью векторизован и выполняется за один проход по массивам.

Исправление ошибок реализуется следующим образом:

def correct_errors(received, error_positions, error_values):

    received = np.array(received, dtype=np.int32)

    for pos, val in zip(error_positions, error_values):

        received[pos] ^= val

    return received

Результаты и обсуждения

В ходе тестирования получены результаты ускорения вычисления синдромов до 20 раз, поиск Ченя имеет ускорение до 50 раз, а полное декодирование ускорено в 10-30 раз относительно стандартной реализации. На рисунке 1 представлено сравнение времени выполнения основных этапов декодирования для классической реализации на языке Python и оптимизированной версии с использованием библиотеки NumPy.

Рисунок 1. Сравнение производительности реализаций декодера RS(544,514)

Как видно из графика, наибольшее ускорение достигается на этапе поиска по методу Ченя и вычисления синдромов, что обусловлено эффективной векторизацией операций.

Заключение

Полученные результаты подтверждают эффективность предложенного подхода и его применимость для задач цифровой обработки сигналов.

Список литературы:

1. Графов О.Б., Егоров С.И., Титов В.С. Мягкое декодирование кодов Рида Соломона // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. – 2012. №2, ч.1. С.17 – 23.
2. Локтионов Е.И., Егоров С.И. Декодер кода Рида-Соломона для сети Ethernet по стандарту IEEE802.3-2018 / Оптико-электронные приборы и устройства в системах распознавания образов, обраб. изображ. и символьной информ.: Материалы конф. // 17-ая международная науч.-техн конф.-Курск: Юго-Западный гос. ун-т. - 2023. -с.149-151.
3. Егоров С.И. Алгоритм декодирования кодов Рида-Соломона, исправляющий вплоть до n-k ошибок в кодовом слове // Труды РНТОРЭС им. А.С. Попова. Серия: Цифровая обработка сигналов и ее применение. Выпуск XI-1. - Москва, 2009. - С. 27-30.
4. Wu Yingquan. New Scalable Decoder Architectures for Reed-Solomon Codes // IEEE Transactions on communications. - 2015. - No. 8. -pp.2741-2761.
5. Egorov S., Markarian G. Error Correction Beyond the Conventional Error Bound for Reed-Solomon Codes // Journal of Electrical Engineering. – 2003. No. 11-12. P.305-310.