Способ декодирования длинного блокового кода с помощью алгоритма витерби

Изобретение относится к области передачи кодированных сообщений. Технический результат - расширение арсенала технических средств, которые могут быть использованы для декодирования блоковых кодов при одновременном снижении требований к объему памяти декодеров. Он достигается в способе декодирования длинного блокового кода с помощью алгоритма Витерби, в котором поступающий кодовый поток принимают как бесконечный сверточный код и подают его подблоками по n₀ кодовых символов на вход декодера Витерби, причем после приема декодером все кодовых подблоков в декодер подают вновь эти же кодовые подблоки, после чего процесс декодирования прерывается и выбираются символы решений декодера Витерби, которые находятся на расстоянии не менее числа символов от места приема последнего кодового подблока размера n₀, при этом после приема более длинной части кодового потока принятые символы решений по всем путям заменяют на вычисленные символы-решения декодера и заменяют хранимые АВ декодером пути принятой части кодового потока на единственный окончательный вектор-решение и запоминают полное число ближних к месту приема символов, а среднюю часть вектора-решения передают получателю исходного сообщения.

 

Изобретение относится к области передачи кодированных сообщений и может быть использовано, преимущественно, при декодировании длинных блоковых кодов с использованием алгоритма Витерби в условиях большой вероятности ошибки в корректируемых данных.

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

Известны способы и устройства декодирования помехоустойчивых кодов.

Один из известных способов декодирования помехоустойчивых кодов, в том числе, и мажоритарно декодируемых [Овечкин Г.В. и Золотарев В.В. Эффективные алгоритмы помехоустойчивого кодирования для цифровых систем связи. Электросвязь, №9, 2003, с. 34-37] заключается в том, что, информационные символы, передаваемые получателю, направляют в декодер из канала связи, в котором возможно внесение ошибок в цифровое сообщение, вместе с избыточными символами кода, которые преобразуют в символы синдрома, значения которых зависят только от ошибок, произошедших в канале связи, и не зависят от значений информационных символов, передаваемых получателю, и суммируют в декодере с помощью порогового элемента на каждом такте работы после очередного сдвига данных по своим регистрам соответствующие символы в ячейках регистра, определяемых выбранным кодом, а после суммирования производят сравнение результат с пороговым значением, по результатам которого судят о необходимости замены декодируемого информационного символа.

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

Другим близким по технической сущности и достигаемому результату является способ декодирования помехоустойчивого кода [RU 2377722, С1, Н03М 13/43, 27.12.2009], заключается в том, что в декодер направляют из канала связи двоичные и/или недвоичные информационные символы кода вместе с избыточными символами кода, преобразуют их в символы регистра синдрома и направляют в пороговый элемент, где вычисляют оценки значений декодируемых символов на основе символов в ячейках синдрома, определяемых декодируемым помехоустойчивым кодом, сравнивают результат вычислений с пороговым значением и по результатам сравнения принимают решение о необходимости изменения декодируемого информационного символа, причем, символы синдрома направляют в пороговый элемент на такое число тактов его работы относительно момента принятия решения о значении декодируемого символа, какое соответствует количеству символов регистра синдрома на входе порогового элемента, при этом, решение о необходимости изменения информационного символа производят на основе конвейерных вычислений, при которых одновременно принимают на разных стадиях решения относительно целой группы декодируемых символов.

Недостатком этого способа является сложность конвейерного многотактового вычислителя и такая же его неспособность к работе при большом уровне входного шума.

Наиболее близким по технической сущности к предложенному является способ кодирования и декодирования блокового кода с использованием алгоритма Витерби [RU 2608872, Н03М 13/43, 25.01.2017], включающий подачу исходного сообщения с кодовой скоростью R=k₀/n₀ в кодер, содержащий k₀ регистров сдвига длиной K битов каждый, содержимое ячеек которых в соответствии с используемым кодом подают на входы n₀ сумматоров по mod2, с выходов которых кодовые символы подблоками по n₀ символов направляют в канал передачи данных, из которого их подают подблоками по n₀ символов на вход декодера, работающего по алгоритму Витерби, содержащего 2^(K-1)*k0 ячеек памяти для хранения весов разности путей и принятого сообщения, 2^(K-1)*k0 регистров сдвига для хранения выживших путей, 2^K*k0 вычислителей дополнительных весов разности путей, 2^K*k0 вычислителей полных новых разностей путей и 2^k0 устройств сравнения весов путей и выбора пути с наименьшим весом, при этом, кодируемые информационные последовательности разбивают на блоки, которые дополнительно разбивают на k₀ меньших блоков, которые помещают в k₀ регистров кодера для такого же кода, но с увеличенной длиной регистров до величины K+U, U≥K, причем все k₀ регистров после ввода в них информационных символов свертывают циклически соединением выходов последних ячеек каждого их этих регистров с их входами, после чего выполняют K+U синхронных сдвигов всех получившихся циклических регистров, во время которых формируют K+U кодовых подблоков по n₀ кодовых символов, которые направляют в канал, а затем подают подблоками по n₀ кодовых символов на вход декодера Витерби, причем после приема декодером всех K+U кодовых подблоков размера n₀ в декодер подают вновь эти же кодовые подблоки в том же порядке еще не менее двух раз, после чего процесс декодирования прерывается и на выжившем пути минимального веса выбираются (K+U)*k₀ символов решений декодера Витерби, которые находятся на расстоянии не менее 5*K*k₀ символов от места приема последнего кодового подблока размера n₀.

При использовании этого способа на передающем конце системы передачи информации ее кодируют блоковым квазициклическим кодом длины n с использованием порождающего многочлена сверточного кода существенно меньшей длины К, так что nR>>K, где R - кодовая скорость применяемого блокового кода.

На приемном конце системы передачи информации декодер, реализующий алгоритм Витерби, работает так же, как и при обычном декодировании исходного длинного сверточного кода с произвольного места. Он принимает первый подблок кодовых символов и обрабатывает их в соответствии с правилами алгоритма декодирования Витерби. Затем принимает следующий такой же блок и т.д.

Поскольку по каналу передачи информации передаются символы двоичного блокового квазициклического кода более длинного, чем исходный сверточный код, то после приема и обработки последнего кодового подблока этого блокового кода размером n в декодер снова подают циклически первый подблок из уже принятых кодовых символов этого кода, затем второй и т.д. В зависимости от длины кода и уровня шума в декодер можно циклически подать m=2÷5 или более раз все кодовые символы принятого кодового блока в зависимости от кода и уровня шума канала.

Однако, поскольку у квазициклического кода нет условного начала, то алгоритм декодирования, как и в случае бесконечного сверточного кода, обеспечивает выход на правильное решение только после прихода в декодер D~(3÷20)K первых кодовых подблоков.

После приема указанных D=(3÷20)K кодовых подблоков, когда алгоритм Витерби сверточного кода обеспечит выход на уровень достаточно достоверных решений относительно декодируемого кодового потока, решения декодера обязательно повторяются с периодом nR. Поэтому, учитывая тот факт, что декодируется не бесконечное сообщение, а блок с nR двоичными информационными символами, получателю информации можно передать только двоичный информационный блок длины nR из середины обработанной декодером Витерби последовательности несколько большей общей длины mnR.

Наиболее близкое решение имеет серьезный недостаток. Для реализации способа блоковый АВ декодер должен хранить все 2^(K-1) путей, отслеживаемых в процессе работы, а их длина составляет mnR битов. Это означает, что при необходимости декодирования длинных кодов размер памяти, которую использует такой блоковый АВ декодер, должен иметь порядок M~mnR2^(K-1) Для больших значений n, что характерно для длинных кодов, это может составить многие сотни Гигабитов, что неоправданно усложняет аппаратуру декодирования.

Задачей, которая решается в изобретении, является разработка способа декодирования длинного блокового кода при использовании алгоритма Витерби при снижении требовании к сложности декодеров, в частности, к объему их памяти.

Требуемый технический результат заключается в расширении арсенала технических средств, которые могут быть использованы для декодирования длинных блоковых кодов с использованием алгоритма Витерби при одновременном снижении требований к сложности реализуемых способов декодирования, в частности, к объему их памяти.

Поставленная задача решается, а требуемый технический результат достигается тем, что, согласно способу декодирования длинного блокового кода с помощью алгоритма Витерби, заключающемуся в том, что, поступающий кодовый поток принимают как бесконечный сверточный код и подают его подблоками по n₀ кодовых символов на вход декодера Витерби, причем после приема декодером всех K+U кодовых подблоков размера n₀ в декодер подают вновь эти же кодовые подблоки в том же порядке еще не менее двух раз, после чего процесс декодирования прерывается и на выжившем пути минимального веса выбираются (K+U)*k₀ символов решений декодера Витерби, которые находятся на расстоянии не менее 5*K*k₀ символов от места приема последнего кодового подблока размера n₀, согласно изобретению, после приема более длинной части кодового потока, чем длина порождающего полинома сверточного кода K, K≤≤nR, символы решений декодера по всем путям заменяют на вычисленные символы-решения декодера и заменяют хранимые пути принятой части кодового потока всего кода на единственный окончательный вектор-решение и запоминают полное число ближних к месту приема символов решения декодера из принятой части кодового потока, а среднюю часть окончательного вектора-решения из нее передают получателю исходного сообщения.

Приведем пример реализации предложенного способа.

Принимаемый кодовый поток подается в блоковый АВ декодер и далее принимается как бесконечный сверточный код. Поскольку блоковый АВ декодер работает, как бы, с бесконечной входной последовательностью, то после приема самых первых символов декодируемого сообщения в ближайшей окрестности от места начала приема символов из канала значения решений АВ декодера в большинстве позиций и по всем хранимым путям содержат много ошибочных значений. И только на достаточном удалении D от места приема символов из канала доля ошибок АВ декодера становится малой в соответствии с выбранными корректирующими возможностями кода для АВ декодера. Это следует, в частности, из [В.В. Золотарев, Г.В. Овечкин. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник. М., "Горячая линия - телеком", 2004, с. 67-68,] где иллюстрируется процесс сходимости решений сверточного АВ декодера к правильным значениям, т.е. с малым числом ошибок на достаточном удалении от места приема кодовых символов из канала. Следовательно, в блоковом АВ декодере на достаточном удалении D~(3-10)K от начала приема символы всех хранимых путей декодера будут, в основном, правильными и одинаковыми. Еще более точные и правильные их значения можно получить разными методами, например, мажоритарными. А это значит, что можно не хранить экспоненциально большое число полных длинных путей. Можно на расстоянии D от места приема кодовых символов из канала выполнить уточняющие вычисления, которые достаточно несложные и затем хранить только эти (mnR-D) символов условно окончательных решений АВ декодера до завершения процедуры декодирования m раз принятого блока, а затем выбрать требуемые символы из середины этой уже единственной хранимой последовательности. В этом случае новый требуемый объем памяти такого блокового АВ (БАВ) декодера будет всего M₀~D2^(K-1)<<M. При больших длинах n блоковых кодов это, с одной стороны, будет в десятки и сотни раз экономить память БАВ декодеров, которую уже не надо доводить до сотен Гбитов. Но, кроме того, такой БАВ декодер свободно декодирует блоковые коды произвольно большой длины, т.к. его память всегда будет размером порядка М₀.

Этим и достигается требуемый технический результат, при котором обеспечивается большая экономия памяти БАВ декодера и одновременно обеспечивается возможность декодировать блоковые коды произвольной длины. При этом остается важным, чтобы величина D длины полностью хранимых путей в декодере была достаточной, чтобы формируемый в улучшенном блоковом АВ декодере вектор окончательных решений действительно почти не отличался от истинного оптимального решения.

Проверка предлагаемого технического решения была осуществлена при компьютерном моделировании блокового кода длины n=1000 для порождающего полинома длины K=15. В результате этого выяснилось, что даже при достаточно тяжелом для декодера отношении относительной энергетики гауссовского двоичного канала (АБГШ канала) E_b/N₀=1,5 дБ решения исходного оптимального БАВ декодера практически всегда совпадали с решениями декодера, работающего по предложенному модифицированному алгоритму с сильно сокращенным объемом памяти при всех 2¹⁴=16384 хранимых отрезках путей от места приема символов длиной D≥200 битов.

Имевшие место различия не увеличивали вероятность ошибки на бит проверяемого декодера более, чем в 1,23 раза при нескольких экспериментах достаточно большой длительности с общим числом переданных символов более 3 млн информационных символов. Это несомненно хороший результат при сопоставлении известного и предложенного способов. Для более низкого уровня шума характеристики обоих декодеров оказывались практически одинаковыми.

При рассмотрении блоковых кодов длины n=2000 и n=4000 с тем же полиномом К результаты декодирования также не менялись. Эти данные в совокупности полностью подтверждают правильность предлагаемого технического решения, которое многократно расширяет реальную сферу применения блоковых кодов с оптимальным декодированием по блоковому алгоритму Витерби при реальных минимально необходимых объемах используемой памяти в декодере.

Способ декодирования длинного блокового кода с помощью алгоритма Витерби, заключающийся в том, что поступающий кодовый поток принимают как бесконечный сверточный код и подают его подблоками по n₀ кодовых символов на вход декодера Витерби, причем после приема декодером всех кодовых подблоков по n₀ кодовых символов в декодер подают вновь эти же кодовые подблоки в том же порядке еще не менее двух раз, после чего процесс декодирования прерывается и на выжившем пути минимального веса выбираются символы решений декодера Витерби, которые находятся на расстоянии не менее числа символов от места приема последнего кодового подблока размера n₀, отличающийся тем, что после приема более длинной части кодового потока, чем длина порождающего полинома сверточного кода в квазициклическом коде, символы решений АВ декодера по всем путям заменяют на вычисленные символы-решения декодера и заменяют хранимые пути принятой части кодового потока всего кода на единственный окончательный вектор-решение и запоминают полное число ближних к месту приема символов из принятой части кодового потока, а среднюю часть окончательного вектора-решения из нее передают получателю исходного сообщения.