Способ кодирования и декодирования блокового кода с использованием алгоритма Витерби Российский патент 2017 года по МПК H03M13/41 

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

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

Известен способ кодирования [RU 2551207, C2, H04N 19/105, 20.05.2015], который содержит этапы, на которых кодируют блок В пикселей с использованием опорного режима и одного или более опорных изображений и тем самым предоставляют закодированный блок В_е, получают одиночный синтаксический элемент, идентифицирующий опорный режим и одно или более опорных изображений, причем одиночный синтаксический элемент представляет запись в первом предопределенном опорном списке, и причем первый список содержит одну или более записей, идентифицирующих, по меньшей мере, одно из множества опорных изображений и одиночного опорного изображения, предоставляют одиночный синтаксический элемент декодеру блока В_е, а особенностью способа является то, что синтаксический элемент получается посредством того, что используемый опорный режим и одно или более опорных изображений отображают на синтаксический элемент в соответствии с предопределенной схемой отображения, каждая запись в первом списке дополнительно идентифицирует опорный режим, одиночный синтаксический элемент дополнительно представляет опорный режим и запись во втором предопределенном опорном списке.

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

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

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

Способ кодирования и декодирования по алгоритму АВ [В.В. Золотарёв, Г.В. Овечкин. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник. М., "Горячая линия - телеком", 2004, 124 с., с. 23] заключается в следующем.

Для длины кода K в случае, например, использования кода с кодовой скоростью R=1/2, на каждом такте работы кодера, представляющего собой двоичный регистр сдвига длиной K битов, вводят очередной информационный символ, а в канал отправляют n₀=2 кодовых символа, образующие кодовый подблок, которые являются суммами по mod2 заданных информационных символов сдвигового регистра, конкретные позиции которых определяют используемый сверточный код, а на приемном конце линии связи одновременно запоминают для такого кода 2^K-1 возможных информационных сообщений и в процессе передачи выбранным кодом запоминают пути длиной 5*K или более.

Декодер АВ работает следующим образом. Сначала в массиве памяти, в которой накапливают величины веса разностей (отличий) запоминаемых путей от принятых сообщений, нулевая последовательность получает вес 0, а все остальные 2^K-1-1 путей получают большой вес, например 1000, что позволяет правильно хранить нужные пути. Далее, при каждом поступлении каждого кодового подблока (в нашем примере - размером n₀=2 битов) декодер вычисляет для каждого пути, который он хранит, 2 варианта возможных продолжений пути (0 или 1) и вычисляет для каждого из них приращение веса разностей путей и принятого подблока, а затем новые 2 варианта приращений путей и их новые полные веса с учетом обоих вариантов их приращений. Полученные 2^К путей группируются на пары, в которых все информационные символы, кроме находящихся на расстоянии K от позиции обрабатываемого в данный момент подблока, совпадают. В каждой паре таких путей, отличающихся в K-ом бите, выбирается тот из них, который имеет меньший вес разности с принятым сообщением, после чего количество выживших путей становится снова равным 2^K-1. Когда длины запоминаемых путей достигают порядка ~5*K, крайний бит того пути, который имеет минимальный вес, считается декодированным и передается получателю, и больше длина запоминаемых путей не растет. Затем принимают следующий подблок и процесс декодирования продолжается.

Процесс может быть прерван в любой момент. Тогда последние примерно ~5*K информационных символов не будут декодированы или будут переданы получателю с ошибками. Во втором варианте после завершения передаваемого сообщения в кодер вводятся еще K-1 нулей, что потребует приема еще такого же дополнительного числа кодовых подблоков. Это сохранит высокую достоверность декодирования всего сообщения.

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

Однако очень существенно и при создании технических средств очень неудобно, что дополнительные символы в конце сообщения конечной длины меняют кодовую скорость исходного сверточного кода. Например, при длине исходного сообщения, равного 100 битам, для кода с R=1/2 в канал должны уходить не 200 двоичных кодовых символов, а еще (K-1)*2 символов, где K - количество ячеек кодирующего регистра. Поэтому, например, в частном случае при K=3 в канал дополнительно уходят 4 кодовых символа. Это значит, что реальная кодовая скорость равна не R=1/2, что было бы крайне удобно при формировании управляющих воздействий (тактовых импульсов) для аппаратуры, использующей декодеры Витерби, a R=100/204=0,490196…, что неоправданно усложняет разработку систем с аппаратурой кодирования.

Именно поэтому возникает задача, которая решается в предложенном изобретении, разработки такого способа кодирования и последующего декодирования сообщений при помехоустойчивом кодировании, когда обеспечивается работа декодеров при той же кодовой скорости R, что и у сверточного кода, выражаемой отношением небольших целых чисел, т.е. нужны блоковые коды с хорошим декодированием, имеющие те же удобные простые значения кодовых скоростей, что и у сверточных, например R=1/2, R=1/3, R=3/4 и т.д. Это существенно упростило бы применение кодирования с использованием АВ для конечных по длине сообщений, т.е. для блоковых кодов.

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

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

Эта задача решается с учетом и использованием важного свойства АВ, которое состоит в том, что в бесконечном сверточном коде (длиной тысячи и миллионы символов) АВ всегда может начинать работу в произвольном месте с приема любого кодового подблока длины n₀, а не только с самого начала передачи очередного такого длинного сообщения. Работая далее в обычном режиме, начиная с некоторого места передаваемой сколь угодно длинной кодовой последовательности после приема из канала примерно 5K÷30K кодовых подблоков, АВ выходит на правильное решение и далее успешно декодирует и остальную часть принимаемой последовательности. Точное число блоков, после приема которых АВ выходит на правильный (с минимальной вероятностью ошибки) путь, зависит от выбора конкретного кода и от уровня шума в канале.

Поставленная задача решается, а требуемый технический результат достигается тем, что в способе кодирования и последующего декодирования сообщений, включающего подачу исходного сообщения в кодер с кодовой скоростью 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₀.

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

Устройство кодирования информации содержит двоичный регистр сдвига длины K, к выходу которого присоединен вход двоичного сдвигового регистра длины U, а выход этого регистра соединен со входом двоичного регистра сдвига длины K. В результате, формируется циклический регистр 1 сдвига длины K+U, обеспечивающий циклический сдвиг записанных в него данных. Содержимое ячеек в соответствии с используемым кодом подают на входы n₀ сумматоров 2 по mod2, выполненных с возможностью передачи формируемых ими n₀ кодовых символов в канал передачи данных.

Это устройство кодирования (кодер) информации блоковым квазициклическим кодом работает следующим образом.

В кодер во все K+U двоичных ячеек записывают информационные символы, предназначенные для помехоустойчивого кодирования и последующей передачи по шумящему каналу связи.

Затем производится главная процедура подготовки к передаче сообщения: кодирование блока из K+U информационных символов для формирования кодового блока, предназначенного для передачи по каналу связи с высоким уровнем шума. Для этого с выхода n₀ полусумматоров 2 кодера их содержимое отправляется в канал связи, затем содержимое всего регистра 1 длины K+U сдвигается циклически на k₀ позиций, после чего снова с выхода n₀ полусумматоров 2 кодера содержимое отправляется в канал и т.д. Этот процесс формирования блокового кода с R=k₀/n₀ заканчивается, когда после (K+U)/k₀ циклических сдвигов регистр 1 сдвига кодера оказывается в исходном состоянии, кодирование блоковым кодом считается законченным и все сформированное кодовое слово блокового кода оказывается отправленным в канал связи. После этого можно приступить к кодированию этим блоковым кодом с R=k₀/n₀ уже следующего двоичного информационного блока длины K+U и т.д.

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

Особенностью предложенного способа является то, что длина K левой части регистра кодера и длина U его дополнительного правого сдвигового регистра относятся как U/K~2÷30. При меньшем соотношении возникают сложности достижения малых вероятностей ошибки при декодировании, а при большем соотношении излишне увеличивается длина кода и сложность устройства кодирования, а также размеры и сложность декодера, который рассматривается далее.

Опишем теперь работу системы декодирования предлагаемого изобретения.

На приемном конце системы связи декодер, реализующий алгоритм Витерби, сразу начинает работать также, как и при обычном декодировании исходного длинного сверточного кода с произвольного места. Он принимает n₀ кодовых символов и обрабатывает их в соответствии с правилами алгоритма декодирования и затем принимает следующий такой же блок и т.д. Поскольку по каналу передаются символы двоичного блокового квазициклического кода, более длинного, чем исходный сверточный код, но все же короткого, длиной в десятки или сотни символов, то после приема и обработки последнего кодового подблока этого блокового кода размером покодовых символов в декодер снова подаются циклически первый подблок из уже принятых n₀ кодовых символов этого кода, затем второй и т.д. В зависимости от длины кода и уровня шума в декодер АВ можно циклически подать снова 2÷5 или более раз все кодовые символы принятого кодового блока, что зависит от кода и уровня шума канала. Но поскольку у квазициклического кода нет "начала", то алгоритм декодирования, как и в случае бесконечного сверточного кода, будет выходить на правильное решение только после прихода в декодер D~(3÷20)K кодовых подблоков. При этом для правильной реализации декодирования используемого блокового кода нужно в дополнение к этому учесть далее, что в декодер несколько раз поступают одни и те же повторяющиеся последовательности кодовых символов, частично искаженных в канале связи. Но тогда после приема указанных D=(3÷20)K кодовых подблоков, когда, в частности, алгоритм Витерби уже обеспечивает достаточно достоверные решения относительно декодируемого кодового потока, решения декодера обязательно повторяются также с периодом K+U. Поэтому, учитывая тот факт, что декодируется не бесконечное сообщение, а блок с K+U двоичными информационными символами, получателю информации (приемнику) нужно передать только двоичный информационный блок длины K+U, но за пределами первых принятых декодером D кодовых подблоков, где, как указывалось выше, эти решения в основном неправильны. С другой стороны, для алгоритма Витерби также хорошо известно, что другое условие достаточной достоверности решений состоит в том, что такие правильные, в основном, решения декодера формируются не ранее чем после приема L=(5÷25)K кодовых подблоков. Таким образом, декодер должен принять ~L+D+K+U кодовых подблоков и затем передать приемнику K+U двоичных информационных символов, находящихся приблизительно в середине этой последовательности решений декодера, т.к. решения, находящиеся близко к месту приема очередного кодового подблока и близко к месту приема самых первых кодовых подблоков, малодостоверны по сравнению с потенциальными возможностями применяемого кода.

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

Предварительное полное моделирование работы предлагаемой системы кодирования и последующего декодирования действительно показало для широкого диапазона значений длин исходного кода K=3-20 при кодовой скорости R=1/2 успешное оптимальное декодирование блокового кода, которое для различных уровней шума оказывается лишь в 1,3-3 раза по вероятности ошибки менее эффективным, чем при использовании сверточного кодирования с тем же кодом. Это полностью соответствует известному преимуществу сверточных кодов над блоковыми. При этом в сверточном коде сохранилось то же значение кодовой скорости R=1/2, которой соответствовал исходный сверточный код.

Изобретение относится к области вычислительной техники и может быть использовано для коррекции ошибок при передаче, хранении, чтении и восстановлении цифровых данных. Техническим результатом является обеспечение возможности использования в системах кодирования блоковых кодов с согласованными скоростями кодирования и декодирования. Способ содержит подачу исходного сообщения с кодовой скоростью R=k₀/n₀ в кодер, содержащий k₀ регистров сдвига длиной K битов каждый, содержимое ячеек которых в соответствии с используемым кодом подают на входы n₀ сумматоров по mod2, с выходов которых кодовые символы подблоками по n₀ символов направляют в канал передачи данных, из которого их подают подблоками по n₀ символов на вход декодера, работающего по алгоритму Витерби, причем кодируемые информационные последовательности разбивают на блоки, которые дополнительно разбивают на k₀ меньших блоков, которые помещают в k₀ регистров кодера для такого же кода, но с увеличенной длиной регистров до величины K+U, U≥K, при этом все k₀ регистров после ввода в них информационных символов свертывают циклически соединением выходов последних ячеек каждого их этих регистров с их входами, после чего выполняют K+U синхронных сдвигов всех получившихся циклических регистров, во время которых формируют K+U кодовых подблоков по n₀ кодовых символов, которые направляют в канал, а затем подают подблоками по n₀ кодовых символов на вход декодера Витерби. 1 ил.

Способ кодирования и декодирования блокового кода с использованием алгоритма Витерби, включающий подачу исходного сообщения с кодовой скоростью 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₀.