ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ Российский патент 2009 года по МПК H04L1/20 

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

Известны устройства восстановления стираний и исправления ошибок, использующие индексы достоверности символов (оценки надежности символов) для повышения достоверности приема информации (см. Р.Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005, с.103,...,105; а также устройства по патентам РФ на изобретения №№2209519; 2209520; 2256294).

Кроме того, известны способы выработки индексов достоверности принятых двоичных символов на основе стирающего канала связи и использования их в процедуре декодирования систематических кодов с применением метода кластерного анализа (см. Лычагин Н.И., Агеев С.А., Гладких А.А., Васильев А.В. «Системы и средства связи, телевидения и радиовещания», № 1, 2, 2006, С.49-55; Гладких А.А., Тетерко В.В. Применение кластерного анализа при декодировании блоковых кодов // Труды LXI научной сессии Российского НТОРЭС им. А.С. Попова. - Москва, 2006, с.381-383), а также способы использования указанных оценок для получения логарифмического отношения правдоподобия при декодировании кодовых комбинаций (см. Скляр, Бернард. Цифровая связь. Теоретические основы и практическое применение, 2-е издание.: Пер. с англ. - М.: Издательский дом «Вильямс», 2003, с.500-503).

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

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

К недостаткам работы прототипа относятся: использование метрики Хэмминга и полный перебор проверочных соотношений, определяемых проверочной матрицей блокового кода, в ходе применения логарифма отношения правдоподобия. Вместе с этим, известны способы обработки блоковых кодов, которые обеспечивают декодирование таких кодов за пределами их конструктивной корректирующие способности (см. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005, с.219).

Технический результат - повышение достоверности приема информации.

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

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

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

Работа устройства рассматривается на примере систематического кода (n, k, d). Пусть порождающий полином кода g(x)=x⁸+х⁷+х⁶+х⁴+1 и n=15, k=7, d=5. B метрике Хэмминга данный код способен исправить две ошибки или восстановить четыре стирания.

Блок приема 1 регистрирует поступающие сигналы и передает их текущие значения в двоичной форме в накопитель кодовой комбинации 4. Например, с передатчика была отправлена кодовая комбинация кода:

На приеме в блоке 1 эта комбинация выделяется из общего потока данных (показано прямыми обратными скобками) и с возможными ошибками фиксируется в блоке 4. Ошибки выделены курсивом

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

Или в иной форме:

здесь знак ⊕ означает сложение по модулю два.

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

В потоке стираний нестертым в первичной последовательности информационных символов присваивается значение ноль, а стертым позициям символов присваивается значение единица.

Пусть конфигурация стираний для принятого кодового вектора имеет вид:

здесь стертые элементы обозначены единицами, а правильно принятые символы отмечены нулями.

Для определения оценки надежности символа назначаются два скользящих окна размерами К₁ и К₂ битов каждое, при этом К₁=К₂. Окна следуют по выделенной из потока данных последовательности стираний одно за другим, перекрываясь между собой, на интервале одного оцениваемого бита, например, при К₁=К₂=3 получаем:

При каждом новом шаге каждому окну присваивается вес K₁+1 и K₂+1, но если в окно попало i стираний, то вес окна уменьшается на эту величину. Общая оценка определяется как сумма оценок первого и второго окна. Если анализируемый символ - стирание, то от общей оценки отнимется единица. Это усиливает различимость оценок надежности. Таким образом, оценка надежности вычисляется для анализируемого символа , попавшего в оба окна в соответствии с выражением

здесь, R - оценка надежности, К₁, К₂ - ширина оценочных окон, х_i - символы, которые попали в эти окна, а x_t - символ, подлежащий оценке и попавший одновременно в оба окна. При К₁=К₂=3 наибольшей оценкой является оценка с индексом 8, а наименьшей оценкой является оценка с индексом 1.

Выход анализатора сигналов 2 подключен к входу накопителя 3, который накапливает оценки надежности R_j для каждого символа кодовой комбинации. После завершения обработки символов очередной кодовой комбинации оценки R_j из накопителя 3 одновременно с комбинацией из блока 4 считываются в коммутатор проверок 5. Например, при К₁=К₂=3 для анализируемой кодовой комбинации получаем:

Коммутатор проверок 5 запрограммирован на деление n-разрядной комбинации (в примере 15-разрядной комбинации) на три участка. Старшие разряды комбинации находятся слева. Первый участок, состоящий из первых f старших разрядов, предназначен для определения кластера (списка комбинаций, принадлежащих определенной группе). Всего может быть образовано 2^f кластеров (f≤k). Второй участок, представляющий половину разрядов, при четном значении разницы n-f определяет координату Х двумерного Евклидова пространства. В случае нечетного значения n-f координате Х присваивается лишний разряд. Оставшиеся разряды кодовой комбинации определяют третий участок и собственно координату Y.

В коммутаторе проверок 5 для рассматриваемого примера при f=5 получаем:

Все три группы символов коммутатор проверок 5 направляет в блок определения кластера 6 и в блок прямых координат 8.

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

Блок коррекции кластера 7 объединяет данные об оценках надежности каждого символа кодовой комбинации и их информационной значимости. При этом оценка надежности получает знак «плюс», если в накопителе кодовой комбинации 4 ей соответствовала единица и, соответственно, «минус», если в блоке 4 был зафиксирован ноль.

Например, для приведенных выше кодовой комбинации и конфигурации стираний получаем:

Блок коррекции кластера 7 формирует проверочные соотношения в соответствии с проверочной матрицей только для f разрядов, которые определяют номер кластера. В блоке 7 каждое проверочное соотношение обрабатывается по формуле: (-1)^s-1=sign(h_z), где z - номер проверочного соотношения, a s - число сворачиваемых положительных оценок надежности, но только среди информационных разрядов выбранного проверочного соотношения.

Оценки в блоке коррекции кластера 7 корректируются за несколько итераций по принципу подсчета апостериорных вероятностей (принцип Байеса). При этом на первом шаге апостериорная оценка принимается равной нулю. В корректируемой последовательности (среди информационных битов) выбираются два самых ненадежных символа, а остальные сворачиваются. Исходная корректируемая оценка R_j дополняется новой оценкой Q_j, получаемой в ходе работы блока 7. Если в результате работы блока коррекции кластера 7 получены оценки вида |R_j|<|Q_j|, то корректировка осуществляется верно. В любом другом случает у корректируемых символов требуется замена знака. Коррекция осуществляется по формуле:

L(d₁)+L(d₂)≈(-1)^1-s×sign[L(d₁)]×sign[L(d₂)]×min(|L(d₁)|,|L(d₂)|).

Здесь функция sign(•) возвращает знак своего аргумента;

L(d₁) - оценка надежности символа, участвующего в формировании проверочного бита;

L(d₂) - оценка надежности проверочного символа;

n - число сворачиваемых единиц среди информационных разрядов.

Например, в полученной последовательности битов, определяющей номера кластера имеем: +7 -6 -4 -4 +5, следовательно последние три символа требуют корректировки. Блок 7 выбирает наиболее ненадежные символы -4 и -4, для коррекции которых подходит проверочное соотношение х₁⊕х₃⊕х₄=h₅. Заметно, что проверочное соотношение не выполняется. Блок 7 инвертирует (меняет знак) у символа в разряде с меньшим нижним индексом. Получаем: +7 -6 +4 -4 +5. Тогда s=1. Отсюда на первом шаге итерации получаем:

- новое значение апостериорной оценки для символа x₃;

- новое значение для другого символа х₄.

Второй шаг итерации:

- значение коррекции для символа х₃, при этом |R₃|<|Q₃|;

- значение коррекции для символа х₄, условие |R₄|<|Q₄| выполнено. Проверочное соотношение в результате коррекции принимает вид: +7 -6 +12 -12 +5. Блок 7 приступает к корректировке символа х₅. Для этого выбирается проверочное соотношение для h₆, которое не выполняется. Меняется знак у символа с наименьшим индексом достоверности, при этом s=0.

- новое значение апостериорной оценки для символа х₄;

- новое значение для символа х₅.

Второй шаг итерации:

- значение коррекции для символа x₄, при этом |R₄|<|Q₄|;

- значение коррекции для символа х₅, при этом |R₅|<|Q₅|.

Проверочное соотношение для определения кластера принимает окончательный вид: +7 -6 +12 - 20 -12, следовательно, в блоке определения кластера 6 из 2^f возможных кластеров фиксируется кластер с номером 1 0 1 0 0₂=20₁₀. В последующем эта информация используется блоком сравнения 10.

Блок прямых координат 8, работая параллельно с блоками 6 и 7, определяет значения координат Х и Y. На основании индексов достоверности символом блок определяет и в случае необходимости корректирует только старший разряд групп символов, определяющих значение координаты Х в двоичной форме. Например, в блоке 8 зафиксированы следующие данные:

Это означает, что старший разряд координаты Х=11111₂=31₁₀ имеет индекс достоверности, равный 6, а старший разряд координаты Y=1₂=1₁₀ имеет индекс достоверности, равный 7. На этом основании в блоке 8 принимается решение о передаче этих сведений в блок сравнения 10. В случае фиксации для старшего разряда координаты Х низкого индекса достоверности осуществляется попытка повышения индекса за счет логарифма отношения правдоподобия аналогично тому, как это делалось для символов, определяющих номер кластера. Если такая попытка завершается неудачей, все сведения о значениях координат предаются в блок инвариантных координат 9.

Блок инвариантных координат 9 определяет значения координат Х и Y, принимая левые символы каждой координаты за младшие разряды. В этом случае Х_in=11111₂=31₁₀ и Y_in=00001₂=16₁₀, что соответствует обратной записи порождающего полинома кода g(x). Эти данные передаются в блок сравнения 10.

Блок сравнения 10 удерживает в своей памяти сведения о кластерах, прямых координатах комбинаций каждого кластера и инвариантных координатах. Например, для кластера 20 в памяти блока хранятся данные:

X=6, Y=18; Х_in=12, Y_in=9, соответствует комбинации 101000011010010;

X=8, Y=3; Х_in=2, Y_in=24, соответствует комбинации 101000100000011;

X=21, Y=1; X_in=21, Y_in=16, соответствует комбинации 101001010100001;

X=27, Y=16; Х_in=27, Y_in=1, соответствует комбинации 101001101110000.

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

Объем необходимой памяти блока в байтах оценивается выражением n·2^n-8. В соответствии с координатами каждая комбинация на декартовой плоскости занимает зону, определяемую выражением:

(X=0; Y=0 и X=2^k-1; Y=2^k-1);

(X=2^k; Y=2^k и X=2^β-1; Y=2^β-1).

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

Суть получения защитных зон заключается в определении диапазона изменения допустимых границ перемещения точки кодовой комбинации при искажении младших разрядов. Поскольку для координат Х и Y выделяется по пять двоичных разрядов, то при искажении младших разрядов каждой координаты возможно получение максимального значения искажения координаты, равного 11111, или минимального значения 00000. Сочетания максимальных и минимальных значений координат дают четыре числа, которые определяют границы возможных изменений для данного вектора. Следовательно, любые наборы искажений младших разрядов исправляются.

Блок исправления стираний 11 принимает окончательное решение о принятом кодовом векторе. Выход этого блока является информационным выходом декодера.

Таким образом, применение декодера с использованием метода кластерного анализа исключает переборные методы восстановления стираний и позволяет исправить n-k стираний в отличие от декодеров, использующих метрику Хэмминга, которые способны исправить d-1<n-k стирание. Сложность декодера не зависит от кратности исправляемых стираний, а объемы памяти в байтах для большинства кодов, применяемых на практике, определяются соотношением n·2^n-8 не представляют трудностей с точки зрения их реализации.

Декодер с исправлением стираний относится к технике связи и может использоваться при проектировании новых и модернизации существующих систем передачи дискретной информации. Содержит блок приема, один выход которого через анализатор сигналов подключен к накопителю, а другой подключен к входу накопителя кодовой комбинации, выход которого подключен к первому входу блока исправления стираний, вход которого подключен к выходу блока сравнения, при этом первый вход коммутатора проверок подключен к выходу накопителя, а второй вход подключен к выходу накопителя кодовой комбинации, а выход блока коммутатора проверок подключен к одному из входов блока определения кластера и к входу блока прямых координат, один выход которого через блок инвариантных координат подключен к третьему входу блока сравнения, второй вход которого подключен к другому выходу блока прямых координат, при этом первый выход блока определения кластера подключен к входу блока коррекции кластера, выход которого подключен к другому входу блока определения кластера, второй выход которого подключен к первому входу блока сравнения. Технический результат - повышение достоверности приема информации. Применение декодера с исправлением стираний, основанного на использовании метода кластерного анализа, позволяет исправить n-k стираний. Сложность декодера не зависит от кратности исправляемых ошибок и требует объем памяти, определяемый соотношением n×2^n-8. 1 ил.

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