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

Описание патента на изобретение RU2379841C1

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

Известны устройства восстановления стираний и исправления ошибок, использующие индексы достоверности символов (оценки надежности символов) для повышения достоверности приема информации (см. Р.Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 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)=x108542+х+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…,

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

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

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

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

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

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

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

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

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

x14, x13, x12, x11, x10, x9, x8, x7, x6, x5, x4, x3, x2, x1, x0.

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

1 группа x14, x13, x12 - номер кластера;

2 группа x11, x9, x8, x7, x6, x5 - координата X;

3 группа x10, x4, x3, x2, x1, x0 - координата 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=1, х2=0, x3=1. Анализатор номера кластера 6 передает эти данные в анализатор координат 7 и блок исправления стираний 9. Преобразованная последовательность имеет вид:

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

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

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

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

x14⊕x13⊕x11=x9;

x13⊕x12⊕x11=x6;

x14⊕x12⊕x11=x3.

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

x13⊕x12⊕x10=x8;

x14⊕x13⊕x10=x4;

x14⊕x12⊕x10=x0.

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

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

Так как символы x14=1, х13=0, х12=1 после восстановления в блоке 6 достоверны, то решение соответствующих линейных уравнений приводит к исправлению старших разрядов координат. Для координаты X: x14⊕x12⊕zx=x3 или 1⊕1⊕zx=1, следовательно, zx=1, т.е. старший разряд координаты Х не искажен, здесь ⊕ - операция сложения по модулю два. Для координаты Y: x14⊕x12⊕zy=x0 или 1⊕1⊕zy=1, следовательно, zy=1. Произошло исправление ошибки. Для окончательного восстановления комбинации значения младших разрядов координат не играют роли (см. Лычагин Н.И., Агеев С.А., Гладких А.А., Васильев А.В. Системы и средства связи, телевидения и радиовещания, №1, 2, 2006, с.49-55).

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

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

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

Похожие патенты RU2379841C1

название год авторы номер документа
ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ 2007
  • Гладких Анатолий Афанасьевич
  • Черторийский Сергей Юрьевич
  • Тетерко Вадим Владимирович
  • Шакуров Радик Шамильевич
  • Закирова Лилия Рэстемовна
RU2344556C1
СИСТЕМА ИСПРАВЛЕНИЯ СТИРАНИЙ С ЗАЩИТОЙ НОМЕРА КЛАСТЕРА 2012
  • Агеев Сергей Александрович
  • Гладких Анатолий Афанасьевич
  • Егоров Юрий Петрович
  • Саенко Игорь Борисович
  • Солодовникова Дарья Николаевна
  • Шитиков Сергей Павлович
RU2485702C1
ДЕКОДЕР С УПОРЯДОЧЕННОЙ СТАТИСТИКОЙ СИМВОЛОВ 2012
  • Гладких Анатолий Афанасьевич
  • Капустин Дмитрий Александрович
  • Логинова Ксения Евгеньевна
  • Ермолаева Анна Сергеевна
RU2490804C1
ДЕКОДЕР С ОБРАБОТКОЙ СПИСКА БАЗОВОГО КЛАСТЕРА 2015
  • Гладких Анатолий Афанасьевич
  • Ганин Дмитрий Владимирович
  • Жарова Анна Александровна
  • Маштеев Асхат Тальгатович
  • Сорокин Иван Александрович
  • Шамин Евгений Анатольевич
RU2605365C1
УСТРОЙСТВО ВОССТАНОВЛЕНИЯ СТИРАНИЙ 2007
  • Гладких Алексей Анатольевич
  • Гладких Екатерина Анатольевна
  • Агеев Сергей Александрович
  • Кулешов Игорь Александрович
  • Репин Геннадий Александрович
  • Скачков Михаил Михайлович
  • Петров Валерий Владимирович
RU2345493C1
АДАПТИВНЫЙ ДЕКОДЕР ПРОИЗВЕДЕНИЯ КОДОВ РАЗМЕРНОСТИ 3D 2012
  • Осадчий Александр Иванович
  • Гладких Анатолий Афанасьевич
  • Агеев Сергей Александрович
  • Комашинский Владимир Ильич
  • Саенко Игорь Борисович
  • Линьков Иван Сергеевич
  • Солодовникова Дарья Николаевна
RU2500073C1
ДЕКОДЕР ПРОИЗВЕДЕНИЯ КОДОВ РАЗМЕРНОСТИ 3D С ЗАПРОСАМИ 2014
  • Гладких Анатолий Афанасьевич
  • Чилихин Николай Юрьевич
  • Маштеев Асхат Тальгатович
  • Юдина Елена Александровна
  • Чуднов Александр Михайлович
RU2562415C1
ДЕКОДЕР С ПОВЫШЕННОЙ КОРРЕКТИРУЮЩЕЙ СПОСОБНОСТЬЮ 2010
  • Егоров Юрий Петрович
  • Гладких Анатолий Афанасьевич
  • Пятаков Анатолий Иванович
  • Кальников Владимир Викторович
  • Бородина Екатерина Сергеевна
RU2438252C1
ПЕРЕСТАНОВОЧНЫЙ ДЕКОДЕР С СИСТЕМОЙ БЫСТРЫХ МАТРИЧНЫХ ПРЕОБРАЗОВАНИЙ 2019
  • Пчелин Никита Александрович
  • Гладких Анатолий Афанасьевич
  • Климов Даниил Витальевич
RU2718224C1
ЛЕКСИКОГРАФИЧЕСКИЙ ДЕКОДЕР КАСКАДНОГО КОДА 2015
  • Гладких Анатолий Афанасьевич
  • Шагарова Анна Александровна
  • Ал Тамими Таква Флайиих Хасан
RU2619533C2

Реферат патента 2010 года ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ

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

Формула изобретения RU 2 379 841 C1

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

Документы, цитированные в отчете о поиске Патент 2010 года RU2379841C1

УСТРОЙСТВО ВОССТАНОВЛЕНИЯ КОДОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ 2003
  • Гладких А.А.
  • Васильев К.К.
  • Агеев С.А.
  • Егоров Ю.П.
  • Бодров С.А.
  • Маслов А.А.
RU2256294C1
ДЕКОДЕР С ПОВЫШЕННЫМ УРОВНЕМ РАЗЛИЧИЯ ОЦЕНОК НАДЕЖНОСТИ 2001
  • Тетерко В.В.
  • Гладких А.А.
  • Васильев К.К.
  • Визиренко А.Б.
RU2209520C2
ДЕКОДЕР С ИЗМЕНЯЕМЫМ ИНТЕРВАЛОМ СТИРАНИЯ 2001
  • Визиренко А.Б.
  • Тетерко В.В.
  • Гладких А.А.
  • Климентьев П.В.
  • Сергеев В.А.
RU2209519C2
Способ приготовления мыла 1923
  • Петров Г.С.
  • Таланцев З.М.
SU2004A1
Способ производства анодной массы 1983
  • Щукин Валерий Алексеевич
  • Колодин Эдуард Александрович
  • Горелик Алевтина Яковлевна
  • Поконова Юлия Васильевна
SU1168633A1

RU 2 379 841 C1

Авторы

Агеев Сергей Александрович

Гладких Анатолий Афанасьевич

Кержнер Дмитрий Алексеевич

Кулешов Игорь Александрович

Петров Валерий Владимирович

Репин Геннадий Александрович

Служивый Максим Николаевич

Даты

2010-01-20Публикация

2008-07-21Подача