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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Коммутатор проверок 5 запрограммирован на деление n-разрядной комбинации (в примере 15-разрядной комбинации) на три участка. Старшие разряды комбинации находятся слева. Первый участок, состоящий из первых f старших разрядов, предназначен для определения кластера (списка комбинаций, принадлежащих определенной группе). Всего может быть образовано 2f кластеров (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(hz), где z - номер проверочного соотношения, a s - число сворачиваемых положительных оценок надежности, но только среди информационных разрядов выбранного проверочного соотношения.

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

L(d1)+L(d2)≈(-1)1-s×sign[L(d1)]×sign[L(d2)]×min(|L(d1)|,|L(d2)|).

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

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

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

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

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

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

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

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

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

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

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

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

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

- значение коррекции для символа x4, при этом |R4|<|Q4|;

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

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

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

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

Блок инвариантных координат 9 определяет значения координат Х и Y, принимая левые символы каждой координаты за младшие разряды. В этом случае Хin=111112=3110 и Yin=000012=1610, что соответствует обратной записи порождающего полинома кода g(x). Эти данные передаются в блок сравнения 10.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RU 2 344 556 C1

Авторы

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

Черторийский Сергей Юрьевич

Тетерко Вадим Владимирович

Шакуров Радик Шамильевич

Закирова Лилия Рэстемовна

Даты

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

2007-06-07Подача