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

Формула изобретения

Способ кодирования-декодирования каскадной кодовой конструкции в системах передачи данных, согласно которому на передающей стороне к блоку исходной информации добавляют циклическую контрольную сумму, полученный блок кодируют внешним кодом в поле GF(q) (q - алфавит кода) и внутренним кодом, на приемной стороне осуществляют декодирование принятого блока информации с обнаружением и исправлением ошибок, при этом сначала выполняют декодирование внутреннего кода, запоминают последовательность декодированных кодовых слов в массиве декодированных кодовых слов внутреннего кода, запоминают последовательность некорректируемых кодовых слов в массиве некорректируемых кодовых слов внутреннего кода, при этом одновременно запоминают последовательность стертых кодовых слов вместо некорректируемых кодовых слов в массиве декодированных кодовых слов внутреннего кода, далее осуществляют декодирование внешним кодом последовательности декодированных кодовых слов массива декодированных кодовых слов внутреннего кода, в отношении результата декодирования внешнего кода выполняют вычисление и проверку циклической контрольной суммы и в случае положительного результата информацию отдают получателю сообщений, а в случае отрицательного результата производят восстановление последовательности стертых кодовых слов массива декодированных кодовых слов внутреннего кода, отличающийся тем, что для восстановления последовательности стертых кодовых слов вычисляют кандидатов на восстановление, для чего инвертируют по одному биту в каждом некорректируемом кодовом слове, тем самым изменяют расстояния по Хэммингу упомянутых кодовых слов от ближайших разрешенных кодовых слов до r, где r - максимальный радиус непересекающихся сфер вокруг разрешенных кодовых слов, после чего декодируют кодовые слова с инвертированными битами внутренним кодом, при этом осуществляют проверку на первое появление полученной кодовой комбинации, и если проверка обнаруживает, что такая кодовая комбинация была ранее, то процедуру вычисления кандидатов на восстановление выполняют снова, а если такой кодовой комбинации не было, то заменяют стертые кодовые слова декодированными словами, затем выполняют декодирование внешним кодом вновь полученного массива декодированных кодовых слов внутреннего кода и повторяют вычисление и проверку циклической контрольной суммы, и если при проверке обнаруживают искажение кодового блока, то процедуру вычисления кандидатов на восстановление выполняют заново, для этого изменяют комбинацию инвертированных бит в некорректируемых кодовых словах, вновь декодируют кодовые слова с инвертированными битами внутренним кодом, проверяют результат декодирования на первое появление вновь полученной кодовой комбинации, затем декодируют массив декодированных кодовых слов внутреннего кода внешним кодом и выполняют проверку циклической контрольной суммы, при этом операции вычисления кандидатов на восстановление, декодирования внутренним и внешним кодами повторяют до тех пор, пока проверка циклической контрольной суммы не даст положительный результат.

Описание изобретения к патенту

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

Известен способ кодирования-декодирования информации, описанный в патенте США № 6374382 "Сокращенный блочный код для систем каскадного кодирования". Данная система передачи данных использует каскадный код, внешний код которого - код Рида-Соломона (PC), формирующий внешнюю кодовую последовательность на основе исходных данных, внутренний код - сокращенный блочный код (n, k,), причем k=8×i, где i - небольшое целое число, выбираемое для того, чтобы избежать перемежения между внутренним и внешним кодами. Внутренний код (12, 8, 3) представляет собой модифицированный код Хэмминга (15, 11).

Данный внутренний код позволяет исправлять однократные ошибки, но при наличии в принятых словах двух и более ошибок на выходе декодера появляются ошибочные и стертые символы. Внешний код - код Рида-Соломона с минимальным кодовым расстоянием d позволяет декодировать любую конфигурацию, содержащую ошибок и р стираний при условии, что d 2 +р+1. В случае невыполнения этого неравенства декодер PC не сможет правильно декодировать информационную последовательность, что в системах передачи данных без обратной связи приведет к потере информации, а в системах с обратной связью - к переспросу переданного блока данных и, следовательно, к снижению информационной скорости передачи.

Наиболее близким к предлагаемому техническому решению является способ, описанный в патенте РФ № 2310273 "Способ кодирования-декодирования информации в системах передачи данных". Способ может быть реализован в системах передачи данных, у которых на передающей стороне осуществляют кодирование информации внешним кодом Рида-Соломона и внутренним кодом, а на приемной стороне - декодирование с обнаружением и исправлением ошибок. При этом выполняют следующие операции. На передающей стороне к блоку исходной информации добавляют циклическую контрольную сумму, полученный блок кодируют внешним кодом и затем внутренним кодом, в качестве которого используют расширенный код Голея (24, 12, 8), позволяющий исправлять все векторы ошибок веса 3 или меньшего, а также часть ошибок веса 4. Затем на приемной стороне производят декодирование принятого блока информации, для чего сначала выполняют декодирование внутренним кодом, запоминают последовательность декодированных кодовых слов внутреннего кода в массиве декодированных кодовых слов внутреннего кода, запоминают последовательность некорректируемых кодовых слов внутреннего кода в массиве некорректируемых кодовых слов внутреннего кода. При этом одновременно запоминают последовательность стертых кодовых слов вместо некорректируемых кодовых слов в массиве декодированных кодовых слов внутреннего кода. Далее осуществляют декодирование внешним кодом последовательности всех кодовых слов (декодированных и стертых) массива декодированных кодовых слов внутреннего кода, в отношении результата декодирования выполняют вычисление и проверку циклической контрольной суммы (CRC). В случае положительного результата, когда проверка по CRC не выявила наличия искажения кодового блока, информацию отдают получателю сообщений, а в случае отрицательного результата, когда проверка по CRC обнаружила искажение кодового блока, производят восстановление последовательности стертых кодовых слов массива декодированных кодовых слов внутреннего кода. Для этого по заранее созданной таблице для каждого некорректируемого кодового слова массива некорректируемых кодовых слов внутреннего кода находят по шесть кандидатов и дополняют ими массив некорректируемых кодовых слов внутреннего кода. Затем для каждого некорректируемого кодового слова производят выбор кандидата в массиве некорректируемых кодовых слов внутреннего кода, заменяют стертые кодовые слова массива декодированных кодовых слов внутреннего кода выбранными кандидатами, после чего повторяют декодирование внешним кодом вновь полученной последовательности массива декодированных кодовых слов внутреннего кода. Процедуры восстановления стертых кодовых слов внутреннего кода и декодирования внешним кодом повторяют до тех пор, пока проверка циклической контрольной суммы не даст положительный результат.

Описанный способ предполагает хранение таблицы из слов кода Голея, находящихся на расстоянии Хэмминга, равному, четырем от разрешенных кодовых слов (разрешенными являются слова на выходе кода Голея, напрямую соответствующие всем возможным входным словам), и для каждого из них - таблицы из шести ближайших разрешенных кодовых слов Голея, находящихся на одинаковом расстоянии Хэмминга от этих слов. Расчеты показывают, что общее количество всех возможных кодовых комбинаций составляет V_all=2²⁴ (так как слово на выходе кодера Голея состоит из 24 бит), из них разрешенных кодовых слов - 2 ¹² (так как слово на входе кодера Голея состоит из 12 бит). Количество исправляемых кодом Голея комбинаций, т.е. комбинаций, находящихся на расстоянии Хэмминга 3 от разрешенных кодовых слов, составляет , где C - количество сочетаний. Тогда количество стертых кодовых слов составит V_all-V_decoded=16777216-9523200=7254016. Количество некорректируемых слов равно количеству стертых. Для каждого некорректируемого кодового слова необходимо хранить таблицу из шести ближайших разрешенных кодовых слов Голея. Суммарное количество некорректируемых и шести разрешенных кодовых слов для каждого из них составит 7×7254016=50778112. Так как каждое кодовое слово кода Голея состоит из 24 бит (трех байт), то общий объем памяти, необходимой для хранения таблицы, составит 152334336 байт (145,2773 Мбайт).

Передача данных по каналам с быстро изменяющимися параметрами (например, по коротковолновому радиоканалу) требует постоянного контроля за состоянием канала и своевременного реагирования на изменившиеся условия распространения сигнала. Таким образом, требуется постоянно в режиме реального времени подстраивать параметры системы передачи данных под текущие условия распространения сигнала. Существует множество способов подстройки параметров системы передачи данных - изменение вида и параметров модуляции, изменение энергетических характеристик передачи, изменение частоты передачи. Одним из важных способов является также и изменение вида и параметров кодовой конструкции. Оценку параметров канала связи необходимо производить после каждого принятого блока данных. Кроме того, по каналу обратной связи необходимо сообщать передающей стороне о качестве канала связи и о необходимости внесения соответствующих изменений в параметры системы передачи данных. После получения такого служебного сообщения передающей стороне необходимо передавать следующий блок данных с измененными параметрами. Тенденции развития современных систем передачи данных таковы, что время между получением очередного блока данных и началом передачи по обратному каналу ответного служебного сообщения составляет десятки миллисекунд. За это время необходимо обработать принятый блок, произвести оценку параметров канала и сформировать служебное сообщение. При этом обработку принятого блока данных необходимо производить не только с теми параметрами, которые были указаны в последнем служебном сообщении, но и с предыдущими, поскольку последнее служебное сообщение могло быть не принято на передающей стороне. Таким образом, время, затрачиваемое на смену параметров кода, должно быть не более 10÷20 миллисекунд. Объем оперативной памяти, требуемой для функционирования описанного в патенте РФ № 2310273 способа, составляет 145,2773 Мбайт, что исключает возможность загрузки за указанное время необходимой таблицы из внешних источников. В то же время современные микропроцессорные устройства не имеют достаточного объема оперативной памяти для одновременного хранения таких таблиц с большим количеством различных кодовых конструкций. Это не позволяет адаптивно менять кодовую конструкцию в процессе передачи данных в зависимости от текущей помеховой обстановки.

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

Поставленная задача решена при реализации способа кодирования-декодирования каскадной кодовой конструкции в системах передачи данных, согласно которому на передающей стороне к блоку исходной информации добавляют циклическую контрольную сумму, полученный блок кодируют внешним кодом в поле GF(q) и внутренним кодом, на приемной стороне осуществляют декодирование принятого блока информации с обнаружением и исправлением ошибок. При этом сначала выполняют декодирование внутреннего кода, запоминают последовательность декодированных кодовых слов в массиве декодированных кодовых слов внутреннего кода, запоминают последовательность некорректируемых кодовых слов в массиве некорректируемых кодовых слов внутреннего кода. Одновременно запоминают последовательность стертых кодовых слов вместо некорректируемых кодовых слов в массиве декодированных кодовых слов внутреннего кода. Далее осуществляют декодирование внешним кодом последовательности декодированных кодовых слов массива декодированных кодовых слов внутреннего кода. В отношении результата декодирования внешнего кода выполняют вычисление и проверку циклической контрольной суммы и в случае положительного результата информацию отдают получателю сообщений, а в случае отрицательного результата производят восстановление последовательности стертых кодовых слов массива декодированных кодовых слов внутреннего кода. Для восстановления последовательности стертых кодовых слов инвертируют по одному биту в каждом некорректируемом кодовом слове, тем самым изменяют расстояния по Хэммингу упомянутых кодовых слов от ближайших разрешенных кодовых слов до r, где r - максимальный радиус непересекающихся сфер вокруг разрешенных кодовых слов. Далее декодируют слова с инвертированными битами внутренним кодом, при этом осуществляют проверку на первое появление полученной кодовой комбинации и, если проверка обнаруживает, что такая кодовая комбинация была ранее, то процедуру вычисления кандидатов на восстановление выполняют снова. Если же такой кодовой комбинации не было, то заменяют стертые кодовые слова декодированными словами, выполняют декодирование внешним кодом вновь полученного массива декодированных кодовых слов внутреннего кода и повторяют вычисление и проверку циклической контрольной суммы. Если при проверке обнаруживают искажение кодового блока, то процедуру вычисления кандидатов на восстановление выполняют заново. Для этого изменяют комбинацию инвертированных бит в некорректируемых кодовых словах, вновь декодируют слова с инвертированными битами внутренним кодом, проверяют результат декодирования на первое появление такой кодовой комбинации. Затем декодируют массив декодированных кодовых слов внутреннего кода внешним кодом и выполняют проверку циклической контрольной суммы. При этом операции вычисления кандидатов на восстановление, декодирования внутренним и внешним кодами повторяют до тех пор, пока проверка циклической контрольной суммы не даст положительный результат.

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

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

Способ может быть реализован в системе кодирования-декодирования информации, которая содержит последовательно соединенные блок 1 вычисления и добавления циклической контрольной суммы, блок 2 кодирования внешним кодом, блок 3 кодирования внутренним кодом, модулятор 4, канал связи 5, демодулятор 6, блок 7 декодирования внутреннего кода, блок памяти 8 декодированных кодовых слов внутреннего кода, блок 9 декодирования внешнего кода, блок 10 вычисления и проверки циклической контрольной суммы. Система кодирования-декодирования информации содержит также блок памяти 11 некорректируемых кодовых слов внутреннего кода, блок 12 вычисления кандидатов на восстановление и блок 13 проверки на первое появление кодовой комбинации. При этом второй выход блока 10 соединен со вторым входом блока 12, выход которого подключен ко второму входу блока 7, второй выход которого через блок памяти 11 соединен с первым входом блока 12. Второй вход блока памяти 8 соединен с первым выходом блока 13, второй выход которого соединен с третьим входом блока 12, а третий выход блока 7 подключен к входу блока 13.

Предлагаемая система обеспечивает кодирование информации каскадным кодом, состоящим из двух кодов - внутреннего (n, k) и внешнего (N, К), где:

n и N - количество символов на выходе внутреннего и внешнего кодов соответственно;

k и K - количество символов на входе внутреннего и внешнего кодов соответственно.

В качестве внешнего кода могут быть использованы любые коды, исправляющие стирания. В качестве внутреннего кода можно использовать любой код, допускающий стирания. Это означает, что все сферы радиуса r вокруг разрешенных кодовых слов (то есть множества всех слов на расстоянии Хэмминга r от кодовых слов) не пересекаются, но каждое из слов находится на расстоянии, не превышающем (r+1) хотя бы от одного разрешенного кодового слова. Такой код позволяет исправлять все векторы ошибок веса г или меньшего и дает возможность исправлять ошибки веса (r+1). Ошибки веса, большего или равного (r+2), не исправляются никогда. Вследствие чего ошибки веса (r+1) исправляют с помощью перебора кодовых слов, находящихся на расстоянии Хэмминга, равном (r+1) от некорректируемого кодового слова.

Для вычисления циклической контрольной суммы в предлагаемой системе используют алгоритм циклических избыточных кодов - Cyclic Redundancy Codes (CRC). Этот алгоритм представляет собой высокоэффективное средство обнаружения ошибок. Благодаря вычислению циклической контрольной суммы возможно определение искажений данных, так как изменение данных приводит к изменению циклической контрольной суммы. Основным свойством алгоритма является то, что циклическая контрольная сумма изменяется как при искажении одного, так и более битов информационной последовательности. Для уменьшения вероятности ложного набора при вычислении циклической контрольной суммы увеличивают порядок порождающего полинома кода CRC.

Операции кодирования и декодирования информации внешним и внутренним кодами осуществляют программно. Проверку достоверности декодированного блока данных по CRC также осуществляют программно.

Предлагаемый способ кодирования-декодирования каскадной кодовой конструкции в системах передачи данных может быть реализован в системе передачи данных, блок-схема которой представлена на чертеже. Рассмотрим работу данной системы на примере каскадной кодовой конструкции, в которой в качестве внешнего кода используют код Рида-Соломона (PC) над полем GF (2¹² ), а в качестве внутреннего - код Голея (24, 12, 8).

На передающей стороне к исходной информационной последовательности, поступающей от источника сообщений, добавляют циклическую контрольную сумму (блок 1). Полученную последовательность (исходная информация вместе с добавленной к ней циклической контрольной суммой) кодируют внешним кодом (блок 2) и затем внутренним кодом (блок 3). Далее закодированную последовательность модулируют (блок 4) и передают в канал связи (блок 5), откуда она поступает на демодулятор (блок 6). После демодулятора принятая последовательность поступает на декодер внутреннего кода (блок 7), который может исправить не более r ошибок (для кода Голея - 3). Если в кодовом слове внутреннего кода было более r+1 ошибки (для кода Голея - 4), то результат декодирования будет ошибочным, но декодер не сможет обнаружить наличие ошибки. В этих случаях кодовые слова с выхода декодера запоминают в массиве декодированных кодовых слов внутреннего кода с помощью блока памяти 8. Если же в кодовом слове внутреннего кода была r+1 ошибка, то декодирование такого слова будет невозможно, и это некорректируемое кодовое слово сохраняют в массиве некорректируемых кодовых слов внутреннего кода (блок памяти 11), а в массив декодированных кодовых слов внутреннего кода (блок памяти 8) записывают вместо него последовательность нулей, длина которой согласуется с параметрами кода. Эта последовательность называется стертым кодовым словом. Для кода Голея (24, 12, 8) длина последовательности нулей будет равна двенадцати. Декодирование внутренним кодом продолжают до тех пор, пока не будет набрано необходимое количество символов внешнего кода. Далее декодируют внешним кодом (блок 9) последовательность декодированных и стертых кодовых слов внутреннего кода, хранящуюся в блоке памяти 8. Затем вычисляют и проверяют циклическую контрольную сумму полученной информационной последовательности (в блоке 10). При положительном результате проверки по CRC информацию выдают получателю сообщений (первый выход блока 10). При отрицательном результате проверки производят восстановление стертых слов массива декодированных кодовых слов внутреннего кода (второй выход блока 10). Для этого вычисляют кандидатов на восстановление стертых кодовых слов (блок 12), инвертируя по одному биту в каждом из некорректируемых кодовых слов внутреннего кода, хранящихся в блоке памяти 11. Тем самым изменяют расстояние по Хэммингу от этого кодового слова до одного из разрешенных кодовых слов до r (для кода Голея 3). Затем производят декодирование внутренним кодом вычисленных кандидатов на восстановление (выход блока 12 - второй вход блока 7). Для сокращения вычислительных затрат при проверке гипотез перед дальнейшим декодированием необходимо проверить, не было ли уже такой комбинации кандидатов на восстановление стертых слов на выходе декодера внутреннего кода (третий выход блока 7 - вход блока 13). Если такая комбинация уже была, то вычисляют следующую комбинацию кандидатов на восстановление (второй выход блока 13 - третий вход блока 12). Если же такой комбинации на выходе декодера внутреннего кода 7 не было (первый выход блока 13), то ее записывают вместо стертых символов в блок памяти 8. Затем заново производят декодирование внешним кодом (блок 9) и выполняют проверку по CRC (блок 10). Если ошибку удалось исправить, то информацию отдают получателю сообщений (первый выход блока 10). Если же проверка по CRC опять указала на наличие ошибки (второй выход блока 10), то снова повторяют вычисление очередной комбинации кандидатов на восстановление (второй выход блока 10 - второй вход блока 12). Таким образом, можно перебрать все возможные комбинации для исправления стертых символов. Выбор очередного кандидата на восстановление стертых символов и декодирование выполняют до тех пор, пока CRC не будет равна остатку информационной последовательности, содержащему циклическую контрольную сумму. Таким образом, принятая кодовая последовательность будет полностью декодирована.

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