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

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

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

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

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

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

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

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

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

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

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

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

Проверочная матрица кода имеет вид:

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

101110000101001.

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

…01]1 10 1 0 0 1 0 1 101001[00….

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

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

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

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

…00]001100101000000[00…,

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

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

Каждому интервалу присваивается вес K₁+1 и K₂+1, но если на длине интервала оказалось i стираний, то вес окна уменьшается на эту величину. Общая оценка определяется как сумма оценок первого и второго интервала. Если анализируемый символ - стирание, то от общей оценки отнимется единица. Это усиливает различимость индексов достоверности символов (см. Гладких А.А., Мансуров А.И., Черторийский С.Ю. Статистическая оценка индексов достоверности символов, формируемых в системе с мягким декодированием. // Периодический научно-технический и информационно-аналитический журнал «Инфокоммуникационные технологии», том 6, №1, 2008 г. Поволжская государственная академия телекоммуникаций и информации, г.Самара. - С.39-43). Таким образом, оценка надежности вычисляется для анализируемого символа попавшего в оба окна в соответствии с выражением

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

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

- кортеж стираний из блока 1…00]001100101000000[00…;

- оценки в накопителе 3…]764456464778888[…;

- символы в накопителе 4…]110100101101001[….

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

x¹⁴, x¹³, x¹², x¹¹, x¹⁰, x⁹, x⁸, x⁷, x⁶, x⁵, x⁴, x³, x², x¹, x⁰.

В коммутаторе разрядов 5 для рассматриваемого примера при ƒ=3 получаем комбинации групп разрядов

1 группа x¹⁴, x¹³, x¹² - номер кластера;

2 группа x¹¹, x⁹, x⁸, x⁷, x⁶, x⁵ - координата X;

3 группа x¹⁰, x⁴, x³, x², x¹, x⁰ - координата Y.

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

- комбинация оценок…]764 464647 578888[…;

- комбинация символов…] 110 101011 001001 [….

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

Анализатор номера кластера 6 предназначен для определения степени надежности разрядов кластера. Если все разряды первой из трех групп символов имеют оценки не ниже шести, то считается, что номер кластера с высокой вероятностью будет определен правильно. Если индексы достоверности символов имеют значения ниже семи, блок определения кластера 6 осуществляет однозначную коррекцию символов за счет информации, содержащейся в разрядах с высокими индексами достоверности. Для этого используется процедура одновременного циклического сдвига порождающих полиномов g(x) и h(x). Первый представляет порождающий полином кода, а второй представляет множество комбинаций дуального кода. Комбинации первого полинома будут иметь постоянный вес (в примере этот параметр равен 7), а дуальный код представляет комбинации с другим весом (в примере этот вес равен 8). Анализатор номера кластера 6 определяет, что младший разряд номера кластера имеет индекс достоверности 4, следовательно, запускается система циклических сдвигов порождающих полиномов. Работа системы представлена таблицами 1 и 2. В ходе анализа в этом блоке вычеркиваются те разряды, которые имеют индекс достоверности менее семи. Легко проверить, что полное совпадение по оставшимся разрядам окажется только для единственной комбинации, выделенной в таблице 1. Число сдвигов 11 полинома g(x) однозначно указывает на 5 кластер. Это означает, что х₁=1, х₂=0, x₃=1. Анализатор номера кластера 6 передает эти данные в анализатор координат 7 и блок исправления стираний 9. Преобразованная последовательность имеет вид:

- комбинация оценок…]888 464647 578888 […;

- комбинация символов…]101 101011 001001 [….

Анализатор координат 7, получив последовательность символов и индексов достоверности, проверяет уровень оценок и, если они у старших разрядов координат имеют низкие индексы, передает данные в блок коррекции координат 8. В рассматриваемом примере старший разряд двоичного представления координаты Х имеет индекс достоверности, равный 4, следовательно, этот символ требует коррекции. Старший разряд координаты Y имеет индекс, равный 5, значит, и этот разряд требует коррекции. Для коррекции координат бок 8 оперирует данными проверочной матрицы. Для старших разрядов из проверочной матрицы выбираются следующие соотношения.

Для координаты Х:

x¹⁴⊕x¹³⊕x¹¹=x⁹;

x¹³⊕x¹²⊕x¹¹=x⁶;

x¹⁴⊕x¹²⊕x¹¹=x³.

Для координаты Y:

x¹³⊕x¹²⊕x¹⁰=x⁸;

x¹⁴⊕x¹³⊕x¹⁰=x⁴;

x¹⁴⊕x¹²⊕x¹⁰=x⁰.

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

Для координаты Х лучшим символом является х³, имеющий индекс достоверности, равный 8. Для координаты Y лучшим символом является х⁰, имеющий индекс достоверности, равный 8.

Так как символы x¹⁴=1, х¹³=0, х¹²=1 после восстановления в блоке 6 достоверны, то решение соответствующих линейных уравнений приводит к исправлению старших разрядов координат. Для координаты X: x¹⁴⊕x¹²⊕z_x=x³ или 1⊕1⊕z_x=1, следовательно, z_x=1, т.е. старший разряд координаты Х не искажен, здесь ⊕ - операция сложения по модулю два. Для координаты Y: x¹⁴⊕x¹²⊕z_y=x⁰ или 1⊕1⊕z_y=1, следовательно, z_y=1. Произошло исправление ошибки. Для окончательного восстановления комбинации значения младших разрядов координат не играют роли (см. Лычагин Н.И., Агеев С.А., Гладких А.А., Васильев А.В. Системы и средства связи, телевидения и радиовещания, №1, 2, 2006, с.49-55).

Блок исправления стираний 9 сравнивает данные из блоков 6 и 7 и на выход передает комбинацию 10111, что соответствует переданному информационному вектору. Выход этого блока является информационным выходом декодера.

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

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

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

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