ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ
DECODER WITH ERASURE CORRECTION

Изобретение относится к технике связи и может использоваться при проектировании новых и модернизации существующих систем передачи дискретной информации.
Известны устройства восстановления стираний и исправления ошибок, использующие индексы достоверности символов (оценки надежности символов) для повышения достоверности приема информации (см. Р.Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 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.
10
8
5
4
2
Работа устройства рассматривается на примере систематического кода. Пусть порождающий полином кода g(x)=x+х+х+х+х+х+1 и n=15, k=5, d=7. В метрике Хэмминга данный код способен исправить три ошибки или восстановить шесть стираний.
Проверочная матрица кода имеет вид:
Блок приема 1 регистрирует поступающие из канала связи сигналы и передает их текущие значения в двоичной форме в накопитель кодовой комбинации 4. Например, с передатчика была отправлена кодовая комбинация кода:
101110000101001.
В блоке 1 эта комбинация выделяется из общего потока данных (показано прямыми обратными скобками) и с возможными ошибками фиксируется в блоке 4. Ошибки выделены курсивом.
10
0
1
1
…01]1100101001[00….
Последние десять символов в комбинации являются проверочными.
Кроме того, в блоке приема 1 вырабатывается сигнал стирания, поступающий в виде логической единицы в анализатор сигналов 2 по симметричному интервалу стирания ρ. Вход блока приема 1 является информационным входом устройства. В блоке приема 1 совместный поток информационных символов и поток стираний разделяются, но между ними всегда сохраняется соответствие по номерам разрядов.
В потоке стираний не стертым в первичной последовательности информационных символов присваивается значение ноль, а стертым позициям символов присваивается значение единица.
Пусть конфигурация стираний для принятого кодового вектора имеет вид:
…00]001100101000000[00…,
здесь стертые элементы обозначены единицами, а правильно принятые символы отмечены нулями.
1
2
1
2
1
2
Для определения индекса достоверности символа назначаются два скользящих интервала размерами К и К бит каждый, при этом К=К. Интервалы следуют по выделенной из потока данных последовательности стираний один за другим, перекрываясь между собой, на позиции одного оцениваемого бита, например, при К=К=3 получаем:
1
2
Каждому интервалу присваивается вес K+1 и K+1, но если на длине интервала оказалось i стираний, то вес окна уменьшается на эту величину. Общая оценка определяется как сумма оценок первого и второго интервала. Если анализируемый символ  - стирание, то от общей оценки отнимется единица. Это усиливает различимость индексов достоверности символов (см. Гладких А.А., Мансуров А.И., Черторийский С.Ю. Статистическая оценка индексов достоверности символов, формируемых в системе с мягким декодированием. // Периодический научно-технический и информационно-аналитический журнал «Инфокоммуникационные технологии», том 6, №1, 2008 г. Поволжская государственная академия телекоммуникаций и информации, г.Самара. - С.39-43). Таким образом, оценка надежности вычисляется для анализируемого символа  попавшего в оба окна в соответствии с выражением
1
2
i
1
2
здесь R - индекс достоверности символа, выраженный целым числом, К, K - ширина оценочных интервалов, х- символы, которые попали в эти интервалы, a  - символ, подлежащий оценке. При К=К=3 наибольшей оценкой является оценка с индексом 8, а наименьшей оценкой является оценка с индексом 1.
j
j
1
2
Выход анализатора сигналов 2 подключен к входу накопителя 3, который накапливает индексы достоверности символов (оценки надежности) R для каждого символа кодовой комбинации. После завершения обработки символов очередной кодовой комбинации оценки R из накопителя 3 одновременно с комбинацией из блока 4 считываются в коммутатор разрядов 5. Например, при К=К=3 для анализируемой кодовой комбинации получаем:
- кортеж стираний из блока 1…00]001100101000000[00…;
- оценки в накопителе 3…]764456464778888[…;
10
0
1
1
- символы в накопителе 4…]1100101001[….
ƒ
i
Коммутатор разрядов 5 запрограммирован на деление n-разрядной комбинации на три группы. Старшие разряды комбинации находятся слева. Первая группа, состоящая из первых ƒ старших разрядов, предназначена для определения кластера (списка комбинаций, принадлежащих определенной группе). Всего может быть образовано 2 кластеров (ƒ≤k). Вторая группа, представляющая половину разрядов при четном значении разницы n-ƒ определяет координату Х двумерного Евклидова пространства. В случае нечетного значения n-ƒ координате Х присваивается лишний разряд. Оставшиеся разряды кодовой комбинации определяют третью группу и собственно координату Y. Если обозначить разряды в порядке убывания степеней х, где , то любая кодовая комбинация может быть представлена последовательностью разрядов:
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
x, x, x, x, x, x, x, x, x, x, x, x, x, x, x.
В коммутаторе разрядов 5 для рассматриваемого примера при ƒ=3 получаем комбинации групп разрядов
14
13
12
1 группа x, x, x - номер кластера;
11
9
8
7
6
5
2 группа x, x, x, x, x, x - координата X;
10
4
3
2
1
0
3 группа x, x, x, x, x, x - координата Y.
Заметно, что символы номера кластера и старшие разряды координат размещаются на местах информационных разрядах систематического кода, такой подход обеспечивает лучшее сочетание проверочных соотношений. В результате получаем:
- комбинация оценок…]764 464647 578888[…;
10
1
1
0
- комбинация символов…] 1 1001 01001 [….
Все три группы символов коммутатор разрядов 5 направляет в анализатор номера кластера 6 и в анализатор координат 7.
1
2
3
Анализатор номера кластера 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 […;
1
1
0
- комбинация символов…]101 1001 01001 [….
Анализатор координат 7, получив последовательность символов и индексов достоверности, проверяет уровень оценок и, если они у старших разрядов координат имеют низкие индексы, передает данные в блок коррекции координат 8. В рассматриваемом примере старший разряд двоичного представления координаты Х имеет индекс достоверности, равный 4, следовательно, этот символ требует коррекции. Старший разряд координаты Y имеет индекс, равный 5, значит, и этот разряд требует коррекции. Для коррекции координат бок 8 оперирует данными проверочной матрицы. Для старших разрядов из проверочной матрицы выбираются следующие соотношения.
Для координаты Х:
14
13
11
9
x⊕x⊕x=x;
13
12
11
6
x⊕x⊕x=x;
14
12
11
3
x⊕x⊕x=x.
Для координаты Y:
13
12
10
8
x⊕x⊕x=x;
14
13
10
4
x⊕x⊕x=x;
14
12
10
0
x⊕x⊕x=x.
i
Заметно, что во всех проверочных соотношениях первые два символа считаются после обработки их в блоке 6 достоверными, а неизвестный разряд z, находящийся на третьей позиции левой части уравнений, может быть найден по наиболее надежному представителю правой части уравнений или мажоритарным методом.
3
0
Для координаты Х лучшим символом является х, имеющий индекс достоверности, равный 8. Для координаты Y лучшим символом является х, имеющий индекс достоверности, равный 8.
14
13
12
14
12
3
14
12
0
x
x
x
y
y
y
Так как символы x=1, х=0, х=1 после восстановления в блоке 6 достоверны, то решение соответствующих линейных уравнений приводит к исправлению старших разрядов координат. Для координаты X: x⊕x⊕z=x или 1⊕1⊕z=1, следовательно, z=1, т.е. старший разряд координаты Х не искажен, здесь ⊕ - операция сложения по модулю два. Для координаты Y: x⊕x⊕z=x или 1⊕1⊕z=1, следовательно, z=1. Произошло исправление ошибки. Для окончательного восстановления комбинации значения младших разрядов координат не играют роли (см. Лычагин Н.И., Агеев С.А., Гладких А.А., Васильев А.В. Системы и средства связи, телевидения и радиовещания, №1, 2, 2006, с.49-55).
Блок исправления стираний 9 сравнивает данные из блоков 6 и 7 и на выход передает комбинацию 10111, что соответствует переданному информационному вектору. Выход этого блока является информационным выходом декодера.
Применение в блоке 6 процедуры циклического сдвига порождающих полиномов не может быть отнесено к переборному методу восстановления стираний, поскольку она не требует алгебраических операций, а является тривиальной операцией поразрядного сравнения двух векторов.
Таким образом, применение декодера с использованием метода кластерного анализа позволяет гарантированно исправить n-k стираний в отличив от декодеров, использующих метрику Хэмминга, которые способны исправить всего d-1<n-k стирание. Сложность декодера не зависит от кратности исправляемых стираний.