Патент на изобретение №2379841

(54) ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ

(57) Реферат:

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

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

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

Кроме того, известны способы выработки индексов достоверности принятых двоичных символов на основе стирающего канала связи и использования их в процедуре декодирования систематических кодов с применением метода кластерного анализа (см. Лычагин Н.И., Агеев С.А., Гладких А.А., Васильев А.В. Системы и средства связи, телевидения и радиовещания,

Наиболее близким устройством такого же назначения является устройство восстановления кодовой последовательности (см. патент РФ на изобретения 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]110100101101001[00.

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

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

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

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

00]001100101000000[00,

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

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

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

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

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

– кортеж стираний из блока 100]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³ или 11z_x=1, следовательно, z_x=1, т.е. старший разряд координаты Х не искажен, здесь – операция сложения по модулю два. Для координаты Y: x¹⁴x¹²z_y=x⁰ или 11z_y=1, следовательно, z_y=1. Произошло исправление ошибки. Для окончательного восстановления комбинации значения младших разрядов координат не играют роли (см. Лычагин Н.И., Агеев С.А., Гладких А.А., Васильев А.В. Системы и средства связи, телевидения и радиовещания, 1, 2, 2006, с.49-55).

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

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

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

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

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

РИСУНКИ