Методы сверточного кодирования и декодирования данных на основе алгоритма быстрого преобразования Фурье

Abstract

RU: Штомпель Н.А. Методы сверточного кодирования и декодирования данных на основе алгоритма быстрого преобразования Фурье. – Рукопись. Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.02 – Телекоммуникационные системы и сети. – Украинская государственная академия железнодорожного транспорта, Харьков, 2010. Диссертационная работа посвящена разработке методов сверточного кодирования и декодирования данных с уменьшенной вычислительной сложностью на основе алгоритма быстрого преобразования Фурье для повышения скорости обработки данных в кодере и декодере. Проведенный анализ показал, что в настоящее время известно несколько методов кодирования и декодирования данных, обеспечивающих работу вблизи пропускной способности канала связи, в частности, турбо- та турбоподобные коды. Данные методы имеют значительную вычислительную сложность, что ограничивает их практическое применение в высокоскоростных телекоммуникационных системах. Сверточные коды обеспечивают менее высокий энергетический выигрыш кодирования по сравнению с турбокодами, но они также широко применяются в различных системах передачи данных. Внедрение сверточных кодов с большой длиной кодового ограничения позволяет повысить достоверность переданных данных, но это связано со следующими трудностями: сложность построения «хороших» кодов и высокая вычислительная сложность методов кодирования, а особенно, декодирование данных. Такие проблемы как ограниченность пропускной способности каналов связи, возрастание потоков передаваемых данных, необходимость достоверной передачи данных, увеличение времени обработки данных в кодере и декодере (кодеке) требуют разработки методов сверточного кодирования и декодирования данных с уменьшенной вычислительной сложностью. Из анализа характеристик сверточных кодов следует, что они имеют ряд преимуществ по сравнению с блоковыми кодами. С другой стороны, вычислительная сложность методов построения сверточных кодов с большой длиной кодового ограничения и процессов их кодирования и декодирования остаются достаточно высокими. Установленная связь между сверточными и блоковыми кодами позволяет применять известные результаты из теории блоковых кодов для их исследования. Однако классические методы представления сверточных кодов в виде блоковых кодов не учитывают их алгебраическую структуру, а это ограничивает практическое применение данных методов. Существует метод алгебраического представления сверточных кодов во временной области, устраняющий указанный недостаток. Однако, из теории блоковых кодов известно, что переход в частотную область с помощью преобразования Фурье позволяет уменьшить вычислительную сложность кодера и декодера за счет применения быстрых алгоритмов вычисления свертки и преобразования Фурье. В связи с этим разработан метод алгебраического представления сверточных кодов в виде недвоичных блоковых циклических кодов, отличающийся от известного описанием информационной, обобщенной порождающей и кодовой последовательностей сверточного кода в виде их Фурье-образов, что позволяет разработать новые методы сверточного кодирования и декодирования данных с меньшей вычислительной сложностью. Анализ алгоритмов быстрого преобразования Фурье (БПФ) в конечных полях показал, что наименьшую вычислительную сложность с точки зрения количества операций умножения имеет алгоритм Винограда, поэтому его целесообразно использовать для уменьшения трудоемкости процессов сверточного кодирования и декодирования данных. Установлено, что сверточное кодирование данных во временной области соответствует задаче вычисления конечной линейной свертки. Вычислительная сложность кодирования описывается полиномиальным законом, который не является оптимальным с точки зрения минимизации количества арифметических операций. Для уменьшения вычислительной сложности кодирования в случае, когда длина полного кодового ограничения сверточного кода представляет собой произведение нескольких сомножителей, разработаны методы сверточного кодирования данных на основе алгоритма Агарвала-Кули вычисления свертки и алгоритма БПФ Винограда. Проведенный анализ показал, что метод алгебраического декодирования сверточных кодов во временной области является перспективным, так как он требует фиксированного количества операций при заданной корректирующей способности и может использоваться для декодирования сверточных кодов с большой длиной кодового ограничения. При этом вычислительная сложность декодирования существенно возрастает при больших значениях длины кодового ограничения, что ограничивает область применения данного метода. В связи с этим усовершенствован существующий метод алгебраического декодирования сверточных кодов, отличающийся от известного представлением процесса декодирования в частотной области и применением алгоритма БПФ Винограда; предложенный метод декодирования уменьшает вычислительную сложность декодера за счет сокращения необходимого количества арифметических операций. На основе предложенных методов сверточного кодирования и декодирования данных разработаны их программная и программно-аппаратная реализации. EN: Shtompel N.A. Methods of convolutional coding and decoding data based on fast Fourier transform algorithm. – the Manuscript. Thesis for the degree of candidate of technical sciences, specialty 05.12.02 - Telecommunication systems and networks. - Ukrainian State Academy of Railway Transport, Kharkov, 2010. The thesis is devoted to developing methods for convolutional coding and decoding data with reduced computational complexity based on fast Fourier transform algorithm to improve the speed of data processing in the encoder and decoder. These methods are based on the method of algebraic representation convolutional codes in the form of non-binary block cyclic codes in the frequency domain, describes the information, the synthesis and generating the code sequence of a convolutional code with their Fourier transforms. The methods of the frequency convolutional coding and decoding of data can reduce, respectively, the computational complexity of encoder and decoder using convolutional codes with long code restrictions. Developed software and hardware and software implementation of the proposed methods of convolutional coding and decoding data.