СПОСОБ КОДОВОЙ ЦИКЛОВОЙ СИНХРОНИЗАЦИИ Российский патент 2010 года по МПК H04L7/08 

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

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

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

Известен способ цикловой синхронизации, при котором принятую входную последовательность, представляющую собой сумму по модулю два помехоустойчивого кода нумерующей и синхронизирующей последовательностей, умножают на проверочный полином кода. В результате чего выделяют нумерующую последовательность. Далее осуществляют обнаружение синхронизирующей последовательности. Затем определяют вектор ошибок и осуществляют исправление ошибок в нумерующей последовательности. После этого сравнивают нумерующие и синхронизирующие последовательности с ранее принятыми и в результате сравнения получают определенное число совпадений выделенных нумерующих и синхронизирующих последовательностей с соответствующими нумерующими и синхронизирующими последовательностями ранее принятых кодовых слов, причем, если в результате сравнения числа совпадений с порогом будет превышение числа совпадений некоторого заранее заданного порога совпадений, принимают решение об установлении цикловой синхронизации [Бек Г.В., Богданович В.Н., Киреев О.П. Метод синхронизации сообщений. Сб.: Построение и анализ систем передачи информации. М.: Наука, 1980, стр.84].

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

Наиболее близким к предлагаемому способу является способ кодовой цикловой синхронизации (прототип), заключающийся в том, что принятую входную последовательность, состоящую из нескольких следующих друг за другом слов, каждое из которых представляет собой поразрядную сумму по модулю два помехоустойчивого циклического кода, синхронизирующей последовательности и нумерующей последовательности, сначала умножают на проверочный полином помехоустойчивого циклического кода. В результате умножения получают сумму синдрома помехоустойчивого циклического кода, синхронизирующей последовательности и нумерующей последовательности. Затем полученную сумму умножают на проверочный полином нумерующей последовательности и получают сумму синдрома помехоустойчивого циклического кода и синхронизирующей последовательности. Из этой суммы вычитают синхронизирующую последовательность и получают синдром помехоустойчивого циклического кода. Далее, если синдром помехоустойчивого циклического кода соответствует допустимой комбинации ошибок, выделяют нумерующую последовательность принятого помехоустойчивого циклического кода и сравнивают ее с нумерующими последовательностями ранее принятых помехоустойчивых циклических кодов. В случае превышения числа совпадений нумерующих последовательностей порогового значения, принимают решение о кодовой цикловой синхронизации входной последовательности [патент РФ №2210870 МПК7 H04L 7/08. Зимихин Д.А., Квашенников В.В., Слепухин Ф.В. Способ адаптивной кодовой цикловой синхронизации, приор. 09.08.2001, опубл. 20.08.2003].

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

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

Для достижения цели предложен способ кодовой цикловой синхронизации, заключающийся в том, что принятую входную последовательность, состоящую из нескольких следующих друг за другом слов, каждое из которых представляет собой поразрядную сумму по модулю два помехоустойчивого циклического кода, синхронизирующей последовательности и нумерующей последовательности сначала умножают на проверочный полином помехоустойчивого циклического кода. В результате умножения получают сумму синдрома помехоустойчивого циклического кода, синхронизирующей последовательности и нумерующей последовательности. Затем полученную сумму умножают на проверочный полином нумерующей последовательности и получают сумму синдрома помехоустойчивого циклического кода и синхронизирующей последовательности. Из этой суммы вычитают синхронизирующую последовательность и получают синдром помехоустойчивого циклического кода. Далее, если синдром помехоустойчивого циклического кода соответствует допустимой комбинации ошибок, выделяют нумерующую последовательность принятого помехоустойчивого циклического кода и сравнивают ее с нумерующими последовательностями ранее принятых помехоустойчивых циклических кодов. В случае превышения числа совпадений нумерующих последовательностей порогового значения, принимают решение о кодовой цикловой синхронизации входной последовательности. Новым является то, что при сравнении нумерующей последовательности с раннее принятыми нумерующими последовательностями запоминают число совпадений нумерующей последовательности с ранее принятыми нумерующими последовательностями в одном из F счетчиков совпадений. При совпадении нумерующей последовательности с ранее принятыми нумерующими последовательностями число в соответствующем счетчике совпадений увеличивают на 1, и в случае превышения числа, записанного в соответствующем счетчике совпадений, порогового значения, принимают решение о кодовой цикловой синхронизации входной последовательности. При несовпадении нумерующей последовательности ни с одной из ранее принятых нумерующих последовательностей, в один из m счетчиков совпадений, значение которого равно 0, записывается значение 1. При отсутствии счетчиков совпадений, значение которых равно 0, значение 1 записывают в счетчик с наименьшим числом совпадений. При этом каждому счетчику совпадений присваивают номера от 1 до F, а также свой признак в виде соответствующей нумерующей последовательности и поиск соответствующего счетчика совпадений по нумерующей последовательности выполняют последовательным циклическим выбором счетчиков совпадений по их номерам, начиная с номера счетчика совпадений, в который осуществлялась последняя запись числа совпадений, причем поиск соответствующего счетчика совпадений по нумерующей последовательности выполняют сравнением нумерующей последовательности с нумерующими последовательностями, соответствующими счетчикам совпадений, и при этом поиск счетчиков совпадений, значение которых равно 0 или минимально, и запись значения 1 в счетчики совпадений также выполняют в циклической последовательности номеров счетчиков.

Осуществление способа кодовой цикловой синхронизации рассмотрим на примере цикловой синхронизации помехоустойчивого каскадного кода.

На передающей стороне формируют входную последовательность, которую затем передают на приемную сторону. Для этого на передающей стороне исходное сообщение объемом K m-ичных (m>1) символов вначале кодируют m-ичным помехоустойчивым кодом, например, m-ичным помехоустойчивым кодом Рида-Соломона. Код Рида-Соломона является внешним кодом или кодом первой ступени помехоустойчивого каскадного кода.

В результате кодирования информации получают кодовое слово кода Рида-Соломона (N, K), информационная длина которого равна K, а блоковая - N символов.

Далее информацию кодируют двоичным кодом, например двоичным помехоустойчивым циклическим кодом Боуза-Чоудхури-Хоквингема (БЧХ - коды) с проверочным многочленом h₁(x). Код БЧХ является внутренним кодом или кодом второй ступени помехоустойчивого каскадного кода. Код БЧХ имеет параметры: n - блоковая длина кода, k - информационная длина кода.

Исходной информацией f(x) для каждого слова кода БЧХ являются символы кода Рида-Соломона. В результате кодирования кодом БЧХ всех символов кода Рида-Соломона получают N двоичных слов кода БЧХ (n, k) или двоичную последовательность с₁, длина которой составляет nN бит.

Далее осуществляется поразрядное сложение по модулю два слов кода БЧХ с нумерующей последовательностью c₂. В качестве нумерующей последовательности выбирается двоичный код с блоковой длиной n и информационной длиной k₂, например, код Рида-Маллера (РМ) 1-го порядка (последовательность максимального периода) с проверочным многочленом h₂(x). Между номерами слов БЧХ в каскадном коде и информационной частью нумерующей последовательности (кода РМ) устанавливается взаимно однозначное соответствие. Первое слово БЧХ складывается с последовательностью, полученной в результате кодирования единицы кодом РМ, второе - в результате кодирования двойки и т.д. Такое сложение выполняется со всеми словами кода БЧХ. Если проверочные многочлены суммируемых кодов h₁(x) и h₂(x) взаимно просты и являются делителями двучлена xⁿ+1, в результате будет получено n слов циклического кода БЧХ с блоковой длиной n и информационной длиной k+k₂. Этот код будет иметь вполне определенное гарантированное минимальное кодовое расстояние, определяемое параметрами полученного кода, и обладать корректирующими свойствами.

Третья последовательность c₃, с которой складываются слова БЧХ, будет постоянной для всех слов синхронизирующей последовательности длиной n символов, нарушающей циклические свойства кода БЧХ. Такой последовательностью может быть любая последовательность с хорошими синхронизирующими свойствами и не являющаяся словом кода БЧХ, например, последовательность Баркера или последовательность максимальной длины.

На приемной стороне входную последовательность, сформированную в виде суммы трех последовательностей c₁, c₂ и c₃, используют для кодовой цикловой синхронизации.

В канале связи из-за искажений сигнала возникают ошибки, и на входную последовательность накладывается комбинация ошибок. На приемной стороне входную последовательность сначала умножают на проверочный многочлен h₁(x) помехоустойчивого кода БЧХ. При умножении кода БЧХ на проверочный многочлен h₁(x) по определению кода получается синдром кода. Поэтому в результате умножения входной последовательности на проверочный многочлен h₁(x) получают сумму синдрома кода БЧХ, синхронизирующей последовательности и нумерующей последовательности. Затем полученную сумму умножают на проверочный полином нумерующей последовательности h₂(x) и получают сумму синдрома помехоустойчивого циклического кода и синхронизирующей последовательности. Из этой суммы вычитают синхронизирующую последовательность и получают синдром s(x) кода БЧХ. По синдрому кода s(x) определяют комбинацию ошибок e(x) в коде БЧХ. Это возможно, если кратность ошибок лежит в пределах исправляющей способности кода. Комбинации ошибок e(x) для синдрома s(x) можно вычислить заранее и поместить, например, в таблицу. При этом определение ошибок в коде БЧХ может выполняться с помощью таблицы ошибок, входом которой являются комбинации синдрома s(x), а выходом - комбинации ошибок e(x) в помехоустойчивом коде БЧХ. Для получения таблицы ошибок сначала для всевозможных комбинаций ошибок e(x) вычисляют соответствующие синдромы s(x) кода БЧХ, а затем помещают комбинации ошибок e(x) в таблицу ошибок по адресу s(x). Если синдром s(x) кода БЧХ соответствует допустимой комбинации ошибок, то есть кратность комбинации ошибок e(x) не превышает исправляющей способности кода БЧХ, слово кода БЧХ считается успешно декодированным. Иначе слово кода БЧХ стирается.

Далее выделяют нумерующую последовательность V, соответствующую принятому (нестертому) коду БЧХ. Для этого из результата умножения входной последовательности на проверочный многочлен h₁(x) вычитают синхронизирующую последовательность, синдром s(x) кода БЧХ и комбинацию ошибок e(x). Полученная нумерующая последовательность V соответствует принятому коду БЧХ.

Затем сравнивают нумерующую последовательность с нумерующими последовательностями ранее принятых кодов БЧХ. Ранее принятые нумерующие последовательности записаны в F счетчиках совпадений, которые могут быть представлены числовыми переменными Z(i), i=1…F. Содержимое счетчиков совпадения равно числу совпавших ранее нумерующих последовательностей. Каждому счетчику совпадений Z(i) соответствует признак этого счетчика Q(i), представляющий собой переменную, например символическую переменную, значение которой равно ранее принятой нумерующей последовательности.

Для определения соответствующего счетчика совпадений все признаки счетчиков Q(i) сравниваются с полученной нумерующей последовательностью V. При этом поиск соответствующего счетчика совпадений по нумерующей последовательности выполняется последовательным циклическим выбором счетчиков совпадений по их номерам i, начиная с номера i₁ счетчика совпадений, в который осуществлялась последняя запись числа совпадений. Поскольку наиболее часто записывается правильная нумерующая последовательность, начало проверки номерующих последовательностей счетчиков совпадений со счетчика, в который проводилась последняя запись, сокращает число операций поиска соответствующего счетчика совпадений. Циклический выбор счетчиков совпадений означает, что признаки счетчиков совпадений сравнивают, начиная с номера счетчика совпадений i₁ и до номера F, а затем с номера 1 до номера i₁-1, то есть номер следующего счетчика записывается в виде i=(i+1)mod F+1.

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

если V=Q(i), то Z(i):=Z(i)+1;

если Z(i)>P, то есть кодовая цикловая синхронизация.

Нумерующая последовательность соответствует положению кода БЧХ в каскадном коде и, значит, однозначно определяет начало каскадного кода. Если нумерующая последовательность соответствует числу J, то начало каскадного кода будет начинаться на J кодов БЧХ раньше. Установление цикловой синхронизации означает, что известно начало кода, и входная информация может быть передана на дальнейшую обработку, то есть декодирование.

Немаловажным для реализации способа кодовой цикловой синхронизации является выбор порогового значения P, при достижении которого устанавливают цикловую синхронизацию. Увеличение значения P уменьшает вероятность ложной синхронизации, однако при этом снижается и вероятность правильной синхронизации. Пороговое значение P следует выбирать таким образом, чтобы вероятность установления синхронизации была соизмерима с вероятностью правильного декодирования кода. При использовании каскадного кода с внутренним кодом БЧХ (31, 16), а внешним - кодом Рида-Соломона (32, 16) в канале связи со средней вероятностью ошибки, не превышающем величины 5·10^-2, пороговое значение выбирают равным 3…4.

При несовпадении нумерующей последовательности ни с одной из ранее принятых нумерующих последовательностей, то есть если полученная нумерующая последовательность принята впервые, то в один из m счетчиков совпадений, значение которого равно 0, записывают значение 1. В этом случае начинают подсчет числа вновь принятой нумерующей последовательности. Через количество символов, равное числу символов n в коде БЧХ, значение нумерующей последовательности увеличивают на единицу. При отсутствии счетчиков совпадений, значение которых равно 0, значение 1 записывают в счетчик с наименьшим числом совпадений. Причем поиск счетчиков совпадений, значение которых равно 0 или минимально, также выполняют в циклической последовательности номеров счетчиков.

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

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

Изобретение относится к кодовой цикловой синхронизации и может быть использовано для цикловой синхронизации помехоустойчивых циклических кодов, и, в частности, каскадных кодов. Технический результат - сокращение числа операций и упрощение способа. Способ кодовой цикловой синхронизации заключается в том, что принятую входную последовательность, состоящую из нескольких следующих друг за другом слов, каждое из которых представляет собой поразрядную сумму по модулю два помехоустойчивого циклического кода, синхронизирующей последовательности и нумерующей последовательности, умножают на проверочный полином помехоустойчивого циклического кода и на проверочный полином нумерующей последовательности и получают сумму синдрома помехоустойчивого циклического кода и синхронизирующей последовательности, затем выделяют нумерующую последовательность принятого помехоустойчивого циклического кода, сравнивают ее с нумерующими последовательностями ранее принятых помехоустойчивых циклических кодов и запоминают число совпадений нумерующей последовательности с ранее принятыми нумерующими последовательностями в одном из F счетчиках совпадений, при совпадении нумерующей последовательности с ранее принятыми нумерующими последовательностями число в соответствующем счетчике совпадений увеличивают на 1, и в случае превышения числа, записанного в соответствующем счетчике совпадений порогового значения, принимают решение о кодовой цикловой синхронизации входной последовательности. 3 з.п. ф-лы.

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

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

3. Способ по п.1, отличающийся тем, что поиск счетчиков совпадений, значение которых равно 0 или минимально, и запись значения 1 в счетчики совпадений выполняют в циклической последовательности номеров счетчиков.

4. Способ по п.2, отличающийся тем, что поиск счетчика совпадений по нумерующей последовательности выполняют сравнением нумерующей последовательности с нумерующими последовательностями, которые соответствуют признакам счетчиков совпадений.