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



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

 


Владельцы патента RU 2608872:

Золотарев Валерий Владимирович (RU)

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поставленная задача решается, а требуемый технический результат достигается тем, что в способе кодирования и последующего декодирования сообщений, включающего подачу исходного сообщения в кодер с кодовой скоростью R=k0/n0, содержащий k0 регистров сдвига длиной K битов каждый, содержимое ячеек которых в соответствии с используемым кодом подают на входы n0 сумматоров по mod2, с выходов которых кодовые символы подблоками по n0 символов направляют в канал передачи данных, из которого их подают подблоками по n0 символов на вход декодера, работающего по алгоритму Витерби, содержащего 2(K-1)*k0 ячеек памяти для хранения весов разности путей и принятого сообщения, 2(K-1)*k0 регистров сдвига для хранения выживших путей, 2K*k0 вычислителей дополнительных весов разности путей, 2K*k0 вычислителей полных новых разностей путей и 2k0 устройств сравнения весов путей и выбора пути с наименьшим весом, согласно изобретению кодируемые информационные последовательности разбивают на блоки, которые дополнительно разбиваю на k0 меньших блоков, которые помещают в k0 регистров кодера для такого же кода, но с увеличенной длиной регистров до величины K+U, U≥K, причем все k0 регистров после ввода в них информационных символов свертывают циклически соединением выходов последних ячеек каждого их этих регистров с их входами, после чего выполняют K+U синхронных сдвигов всех получившихся циклических регистров, во время которых формируют K+U кодовых подблоков по n0 кодовых символов, которые направляют в канал, а затем подают подблоками по n0 кодовых символов на вход декодера Витерби, причем после приема декодером всех K+U кодовых подблоков размера n0 в декодер подают вновь эти же кодовые подблоки в том же порядке еще не менее двух раз, после чего процесс декодирования прерывается и на выжившем пути минимального веса выбираются (K+U)*k0 символов решений декодера Витерби, которые находятся на расстоянии не менее 5*K*k0 символов от места приема последнего кодового подблока размера n0.

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

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

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

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

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

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

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

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

На приемном конце системы связи декодер, реализующий алгоритм Витерби, сразу начинает работать также, как и при обычном декодировании исходного длинного сверточного кода с произвольного места. Он принимает n0 кодовых символов и обрабатывает их в соответствии с правилами алгоритма декодирования и затем принимает следующий такой же блок и т.д. Поскольку по каналу передаются символы двоичного блокового квазициклического кода, более длинного, чем исходный сверточный код, но все же короткого, длиной в десятки или сотни символов, то после приема и обработки последнего кодового подблока этого блокового кода размером покодовых символов в декодер снова подаются циклически первый подблок из уже принятых n0 кодовых символов этого кода, затем второй и т.д. В зависимости от длины кода и уровня шума в декодер АВ можно циклически подать снова 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=k0/n0 в кодер, содержащий k0 регистров сдвига длиной K битов каждый, содержимое ячеек которых в соответствии с используемым кодом подают на входы n0 сумматоров по mod2, с выходов которых кодовые символы подблоками по n0 символов направляют в канал передачи данных, из которого их подают подблоками по n0 символов на вход декодера, работающего по алгоритму Витерби, содержащего 2(K-1)*k0 ячеек памяти для хранения весов разности путей и принятого сообщения, 2(K-1)*k0 регистров сдвига для хранения выживших путей, 2K*k0 вычислителей дополнительных весов разности путей, 2K*k0 вычислителей полных новых разностей путей и 2k0 устройств сравнения весов путей и выбора пути с наименьшим весом, отличающийся тем, что кодируемые информационные последовательности разбивают на блоки, которые дополнительно разбивают на k0 меньших блоков, которые помещают в k0 регистров кодера для такого же кода, но с увеличенной длиной регистров до величины K+U, U≥K, причем все k0 регистров после ввода в них информационных символов свертывают циклически соединением выходов последних ячеек каждого их этих регистров с их входами, после чего выполняют K+U синхронных сдвигов всех получившихся циклических регистров, во время которых формируют K+U кодовых подблоков по n0 кодовых символов, которые направляют в канал, а затем подают подблоками по n0 кодовых символов на вход декодера Витерби, причем после приема декодером всех K+U кодовых подблоков размера n0 в декодер подают вновь эти же кодовые подблоки в том же порядке еще не менее двух раз, после чего процесс декодирования прерывается и на выжившем пути минимального веса выбираются (K+U)*k0 символов решений декодера Витерби, которые находятся на расстоянии не менее 5*K*k0 символов от места приема последнего кодового подблока размера n0.



 

Похожие патенты:

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

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

Изобретение относится к системам последовательного декодирования потоков данных в канале с шумом, в частности к последовательному декодеру Витерби для сверточных перфорированных и неперфорированных кодов со структурой «один вход - несколько выходов» (SIMO).

Изобретение относится к радиосвязи и предназначено для упреждающей коррекции ошибок. .

Изобретение относится к приложениям алгоритма Витерби и, в частности, к усовершенствованным системе и способу осуществления высокоскоростной операции сложения/сравнения/выбора (ССВ) по схеме “бабочка” в реализации алгоритма Витерби.

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

Изобретение относится к радиотехнике, в частности к способам декодирования данных в прямом канале по проекту стандарта UMTS-2000 для второго типа прерывистой передачи.
Наверх