Найти кодовые векторы по информационным блокам (3 видео)

Содержание

Примеры задач с решениями
Код Рида-Соломона
Описание РС-кода и его характеристик
Кодирование сообщений РС-кодом
Декодирование кодов Рида-Соломона
Обнаружение искажений
Проверочная матрица РС – кода
Определение коэффициентов синдромного многочлена
Решение системы линейных уравнений
Формальная производная многочлена в конечном поле
Метод решения ключевого уравнения
Архитектура построения программного комплекса
Заключение
Найти кодовые векторы по информационным блокам
Метричное представление n,k-кодов
Циклические коды
Логический код 4В/5В
Скрэмблирование
Линейные блочные коды
📽️ Видео

Видео:Орт вектора. Нормировать вектор. Найти единичный векторСкачать

Примеры задач с решениями

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

Решение. 1. Значность кодовых комбинаций соответствует количеству разрядов — п. В принятых кодовых комбинациях п_х = п₂ = 4.

2. Вес определяется по количеству «1» в комбинации. В принятых кодовых комбинациях V_x = 1; V₂ =4.
3. Кодовое расстояние между комбинациями определяется как вес суммы по модулю 2 кодовых комбинаций. В принятых кодовых комбинациях d = 000101111 = 1110 = 3.

Задача 2. Принята кодовая комбинация 101011. Известно, что вектор ошибки ё = 101000 . Найти исходную кодовую комбинацию.

Решение. Для нахождения исходной кодовой комбинации определим сумму по модулю 2 для принятой комбинации и вектора ошибки, т.е. «’ = 101011, ё = 101000 , получим « = «’0ё = 1О1О1101О1ООО = ОООО11.

Задача 3. Передана кодовая комбинация 1100. Известно, что вес вектора ошибки V- =2. Найти возможные варианты искаженных комбинаций и кодовое расстояние, необходимое для обнаружения и устранения всех ошибок.

Решение. 1. Возможные варианты искаженных комбинаций состоят из тех комбинаций, которые отличаются от исходной двумя позиционными местами, так как т_е = 2. Возможные варианты искаженных комбинаций: 1010, 1001, ОНО, 0101, 0000.

Проверим комбинации, сложив их по модулю 2 с исходной комбинацией,т.е. ё = а®а‘.Получим ё_х =110001010 = 0110; е₂ =110001001 = 0101; ё₃ =110000110 = 1010; ё₄ =110000101 = 1001; ё₅ = 110000000 = 1100.

2. Для обнаружения и устранения всех ошибок необходимо, чтобы кодовое расстояние составляло d > t + 6 -г 1, где Г — обнаруживаемые ошибки; б — исправляемые ошибки. При разрядности нашего числа

п = 4 могут возникнуть четырехкратные ошибки. Следовательно, для их исправления и обнаружения необходимо, чтобы кодовое расстояние удовлетворяло условию 4 + 4 +1 > 9 , т.е. необходимо увеличить разрядность кода.

Задача 4. Определить корректирующую способность кода, имеющего разрешенные комбинации 00000, 01110, 10101 и 11011.

Видео:Собственные векторы и собственные числа линейного оператораСкачать

Код Рида-Соломона

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

Так, например, для определенного Рида-Соломона кода (РС-кода) необходимо установить:

длину n кодового слова (блока);
количество k информационных и N-k проверочных символов;
неприводимый многочлен р(х), задающий конечное поле GF(2 r );
примитивный элемент α конечного поля;
порождающий многочлен g(x);
параметр j кода;
используемое перемежение;
последовательность передачи кодовых слов или символов в канал и еще некоторые другие.

Здесь в работе рассматривается несколько другая частная задача — моделирование собственно РС-кода, являющаяся центральной основной частью названной выше задачи анализа кода.

Видео:ПРОСТОЙ СПОСОБ, как запомнить Векторы за 10 минут! (вы будете в шоке)Скачать

Описание РС-кода и его характеристик

Для удобства и лучшего уяснения сущности устройства РС-кода и процесса кодирования вначале приведем основные понятия и термины (элементы) кода.

Рида – Соломона коды (РС-код) можно интерпретировать как недвоичные коды БЧХ (Боуза – Чоудхури – Хоквингема), значения кодовых символов которых взяты из поля GF(2 r ), т. е. r информационных символов отображаются отдельным элементом поля. Коды Рида – Соломона – это линейные недвоичные систематические циклические коды, символы которых представляют собой r-битовые последовательности, где r – целое положительное число, большее 1.

Коды Рида – Соломона (n, k) определены на r-битовых символах при всех n и k, для которых:
0 r + 2, где
k – число информационных символов, подлежащих кодированию,
n – число кодовых символов в кодируемом блоке.

Для большинства (n, k)-кодов Рида – Соломона; (n, k) = (2 r –1, 2 r –1–2∙t), где
t – количество ошибочных символов, которые может исправить код, а
n–k = 2t – число контрольных символов.

Код Рида – Соломона обладает наибольшим минимальным расстоянием (числом символов, которыми отличаются последовательности), возможным для линейного кода. Для кодов Рида – Соломона минимальное расстояние определяется следующим образом: dmin = n–k +1.

Определение. РС-кодом над полем GF(q=р m ), с длиной блока n = q m -1, исправляющим t ошибок, является множество всех кодовых слов u_(n) над GF(q), для которых 2t последовательных компонентов спектра с номерами равны 0.

Тот факт, что 2t последовательных степеней α — корни порождающего многочлена g(x) или что спектр содержит 2t последовательных нулевых компонентов, является важным свойством кода, позволяющим исправлять t ошибок.

Информационный многочлен Q. Задает текст сообщения, которое делится на блоки (слова) постоянной длины и оцифровывается. Это то, что подлежит передаче в системе связи.
Порождающий многочлен g(x) РС-кода — многочлен, который преобразует информационные многочлены (сообщения) в кодовые слова путем перемножения Q·g(x)= С =u_(n) над GF(q).

Проверочный многочлен h(x) позволяет устанавливать наличие искаженных символов в слове.
Синдромный многочлен S(z). Многочлен, содержащий компоненты соответствующие ошибочным позициям. Вычисляется для каждого принятого декодером слова.
Многочлен ошибок E. Многочлен с длиной равной кодовому слову, с нулевыми значениями во всех позициях, кроме тех, что содержат искажения символов кодового слова.

Многочлен локаторов ошибок Λ(z) обеспечивает нахождение корней, указывающих позиции ошибок в словах, принятых приемной стороной канала связи (декодером). Корни его могут быть найдены методом проб и ошибок, т.е. путем подстановки по очереди всех элементов поля, пока Λ(z) не станет равным нулю.
Многочлен значений ошибок Ω(z)≡Λ(z)·S(z) (modz 2t ) сравним по модулю z 2t с произведением многочлена локаторов ошибок на синдромный многочлен.

Неприводимый многочлен поля р(x). Конечные поля существуют не при любом числе элементов, а только в случае, если число элементов является простым числом р или степенью q=р m простого числа. В первом случае поле называется простым (его элементы-вычеты чисел по модулю простого числа р), во втором-расширением соответствующего простого поля (его q элементов-многочленов степени m-1 и менее — это вычеты многочленов по модулю неприводимого над простым полем многочлена р(x) степени m)

Примитивный многочлен. Если корнем неприводимого многочлена поля является примитивный элемент α, то р(x) называют неприводимым примитивным многочленом.

В ходе изложения действий с РС-кодом нам потребуется неоднократно обращение к полю Галуа, поэтому сразу здесь поместим рабочую таблицу с элементами этого поля при разных представлениях элементов (десятичным числом, двоичным вектором, многочленом, степенью примитивного элемента).

Таблица П — Характеристики элементов конечного поля расширения GF(2 4 ), неприводимый многочлен p(x) = x 4 +x+1, примитивный элемент α =0010= 2₁₀

Пример 1. Над конечным полем GF(2 4 ), задан неприводимый многочлен поля p(x) = x 4 + x + 1, примитивный элемент α =2, и задан (n, k)- код Рида-Соломона (РС-код). Кодовое расстояние этого кода равно d = n — k + 1 = 7. Такой код может исправлять до трёх ошибок в блоке (кодовом слове) сообщения.

Порождающий многочлен g(z) кода имеет степень m =n-k = 15-9 = 6 (его корнями являются 6 элементов поля GF(2 4 ) в десятичном представлении, а именно элементы 2, 3, 4, 5, 6, 7) и определяется соотношением, т.е. многочленом от z с коэффициентами (элементами) из GF(2 4 ) в десятичном представлении при i = 1(1)6. В рассматриваемом РС-коде 2 9 = 512 кодовых слов.

Кодирование сообщений РС-кодом

В таблице П эти корни имеют и степенное представление .

Здесь z- абстрактная переменная, а α -примитивный элемент поля, через его степени выражены все (16) элементы поля. Многочленное представление элементов поля использует переменную х.
Вычисление порождающего многочлена g(x)=А·В РС-кода выполним частями (по три скобки):

Векторное представление (через коэффициенты g(z) элементами поля в десятичном представлении) порождающего многочлена имеет вид

g(z) = G = (1, 11, 15, 5, 7, 10, 7).

После формирования порождающего многочлена РС-кода, ориентированного на обнаружение и исправление ошибок, задается сообщение. Сообщение представляется в цифровом виде (например, ASCII- кодом), от которого переходят к многочленному или векторному представлению.

Информационный вектор (слово сообщения) имеет k — компонентов из (n, k). В примере k = 9, вектор получается 9-компонентный, все компоненты – это элементы поля GF(2 4 ) в десятичном представлении Q = (11, 13, 9, 6, 7, 15, 14, 12, 10).

Из этого вектора формируется кодовое слово u — вектор с 15 компонентами. Кодовые слова, как и сами коды, бывают систематическими и несистематическими. Несистематическое кодовое слово получают умножением информационного вектора Q на вектор, соответствующий порождающему многочлену

После преобразований получаем несистематическое кодовое слово (вектор) в виде
Q·g = .

При систематическом кодировании сообщение (информационный вектор) представляют многочленом Q(z) в форме Q(z)=q(z)·g(z) + R(z), где степень degR(z) n — k (в примере Z n — k = Z 6 ) и выполняют после сдвига деление Q(z)·Z n — k на g(z). В результате находят остаток от деления R(z). Все операции выполняют над полем GF(2 4 )

(11, 13, 9, 6, 7, 15, 14, 12, 10, 0, 0, 0, 0, 0, 0) =
=(1, 11, 15, 5, 7, 10, 7)·(11, 15, 9, 10,12,10,10,10, 3) + (1, 2, 3, 7, 13, 9) = G·S + R.

Остаток при делении многочленов вычисляется обычным способом (уголком см.здесь Пример 6). Деление выполняется по образцу: Пусть Q = 26, g(z) = 7 тогда 26 = 7·3 +R(z), R(z)=26 -7·3 =26-21 = 5. Вычисление остатка R(z) от деления многочленов. Приписываем к вектору Q справа остаток R.

Получаем u — кодовое слово в систематическом виде. Этот вид явно содержит информационное сообщение в k старших разрядах кодового слова

u = (11,13,9,6,7,15,14,12,10; 1, 2, 3, 7, 13, 9)

Разряды вектора нумеруются справа налево от 0(1)14. Шесть младших разрядов справа являются проверочными.

Декодирование кодов Рида-Соломона

После получения блока декодер обрабатывает каждый блок (кодовое слово) и исправляет ошибки, которые возникли во время передачи или хранения. Декодер делит полученный многочлен на порождающий многочлен кода РС. Если остаток равен нулю, то ошибок не обнаружено, в противном случае — имеют место ошибки.

Типичный РС-декодер выполняет пять этапов в цикле декодирования, а именно:

Вычисление синдромного многочлена (его коэффициентов ), обнаруживаются ошибки.
Решается ключевое уравнение Падэ — вычисление значений ошибок и их позиций соответствующих местоположений.
Реализуется процедура Ченя — нахождение корней многочлена локатора ошибок.
Используется алгоритм Форни для вычисления значения ошибки.
Вносятся корректирующие поправки в искаженные кодовые слова;

Завершается цикл извлечением сообщения из кодовых слов (снятие кода).

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

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

Обнаружение искажений

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

Вычисление синдромного многочлена
Умножение на приемной стороне кодового слова С на проверочную матрицу Н может давать в результате два исхода:

синдромный вектор S=0, что соответствует отсутствию ошибок в векторе C;
синдромный вектор S≠0, что означает наличие ошибок (одной или более) в компонентах вектора C.

Интерес представляет второй случай.

Кодовый вектор с ошибками представлен в виде C(E) =C + E, E– вектор ошибок. Тогда

Компоненты Sj синдрома определяются либо соотношением суммирования
для n = q-1 и j = 1(1)m = n-k, либо схемой Горнера:

Пример 2. Пусть вектор ошибок имеет вид Е = . Он искажает в кодовом векторе символы на 3-й и 10-й позициях. Значения ошибок соответственно 8 и 12 — эти значения также являются элементами поля GF(2 4 ) и заданы в десятичном (табл. П) представлении. В векторе Е нумерация позиций от младших справа налево, начиная с 0(1)14.

Сформируем теперь кодовый вектор с двумя ошибками в 3-ем разряде и в 10-ом со значениями 8 и 12 соответственно. Это осуществляется суммированием в поле GF(2 4 ) по правилам арифметики этого поля. Суммирование элементов поля с нулем не изменяет их значения. Ненулевые значения (элементы поля) суммируются после преобразования их к многочленному представлению, как обычно суммируются многочлены, но коэффициенты при неизвестной приводятся по mod 2.

После получения результата суммирования они вновь преобразуются к десятичному представлению, пройдя предварительно через степенное представление

Ниже показано вычисление искажённых ошибками значений в 10 и 3 позициях кодового слова:

Декодер вычисления выполняет по общей формуле для компонентов Sj, j=1(1)m. Здесь (в модели) используем соотношение , так как E задаём (моделируем) в программе сами, то ненулевые слагаемые получаются только при i = 3 и i = 10.

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

Проверочная матрица РС – кода

Как только сформулирован порождающий многочлен кода, появляется возможность построения проверочной матрицы для кодовых слов, а также определение количества исправляемых ошибок (см.здесь, декодер ). Построим вспомогательную матрицу [7×15], из которой могут быть получены две разные проверочные матрицы: первые шесть строк – одна и последние шесть строк – другая.

Сама матрица формируется специальным образом. Первые две строки очевидны, третья строка и все последующие получены вычитанием из предыдущей (второй) строки отрезка чисел натурального ряда 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 по mod 15. При возникновении нулевого значения оно заменяется числом 15, отрицательные вычеты преобразуются в положительные.

Каждая матрица соответствует своему порождающему многочлену для систематического и несистематического кодирования.

Определение коэффициентов синдромного многочлена

Далее будем определять коэффициенты синдромного многочлена при j=1(1)6.
Относительно кодового слова с длиной , поступающего на вход декодера мы допускаем, что оно искажено ошибками.

Относительно вектора ошибок для его выявления необходимо знать следующее:

количество искаженных позиций у кодового слова
;
номера (положение) искаженных позиций в кодовом слове ;
значения (величины) искажений .

Как вычисляется и используется далее синдромный вектор (многочлен) S? Его роль при декодировании кодовых слов очень значительна. Покажем это с иллюстрацией на числовом примере.

Пример 3. (Вычисление компонентов синдромного вектора >$» data-tex=»inline»/> )

то в итоге имеем >=(S_1,S_2,S_3,S_4,S_5,S_6)$» data-tex=»inline»/> =

Для дальнейшего рассмотрения введем новые понятия. Величину будем называть локатором ошибок, здесь искаженный символ кодового слова на позиции , α – примитивный элемент поля GF(2 4 ).

Множество локаторов ошибок конкретного кодового слова рассматривается далее как коэффициенты многочлена локаторов ошибок σ(z), корнями которого являются значения , обратные локаторам.

При этом выражения обращаются в нуль.

всегда свободный член уравнения всегда свободный член уравнения .
Степень многочлена локаторов ошибок равна v – количеству ошибок и не превышает величины .

Все искаженные символы находятся на разных позициях слова, следовательно, среди локаторов , не может быть повторяющихся элементов поля, а многочлен σ(z)=0 не имеет кратных корней.

Величины ошибок для удобства записи переобозначим символом . Для коэффициентов синдромного многочлена ранее рассматривались нелинейные уравнения. В нашем случае v=1 начало отсчета компонентов синдрома.

где — неизвестные величины, а — известные, вычисляемые на первом этапе декодирования, параметры (компоненты синдромного вектора).

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

Преобразование к системе линейных уравнений

В уравнение многочлена локаторов ошибок подставляется значение его корней . При этом многочлен обращается в нуль. Образуется тождество, обе части которого умножаем на , получаем:

Таких равенств получаем

Суммируем эти равенства по всем , при которых эти равенства выполняются. Так как многочлен σ(z) имеет v корней , раскроем скобки и перенесем коэффициенты за знак суммы:

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

Знаки «–» при вычислениях над двоичным полем опускаются, так как со-ответствуют «+». Полученная система линейных уравнений является ганкелевой и ей соответствует матрица с размерами бит.

Эта матрица не вырождена, если число ошибок в кодовом слове C(E) строго равно , т.е. способность помехоустойчивости данного кода не нарушилась.

Решение системы линейных уравнений

Полученная система линейных уравнений в качестве неизвестных содержит коэффициенты многочлена локаторов ошибок для кодового слова C(E). Известными считаются вычисленные ранее компоненты синдромного вектора . Здесь t – количество ошибок в слове, m – количество проверочных позиций в слове.

Существуют разные методы решения сформированной системы.

Отметим, что матрица (ганкелева) не вырождена для размерностей, ограниченных количеством допустимым в отдельном слове (меньшем 0.5m) ошибок. При этом система уравнений однозначно разрешается, а задача может быть сведена просто к обращению ганкелевой матрицы. Желательно было бы снять ограничение на размерность матриц, т.е. над бесконечным полем.

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

итеративный метод Тренча – Берлекэмпа — Месси (ТБМ-метод); (1)
прямой детерминированный Питерсона — Горенштейна — Цирлера; (ПГЦ — метод); (2)
метод Сугиямы, использующий алгоритм Евклида для нахождения НОД (С-метод).(3)

Не рассматривая других методов, остановим свой выбор на ТБМ-методе. Мотивировка выбора следующая.

Метод (ПГЦ) прост и хорош, но для малого количества исправляемых ошибок, С-метод сложен для реализации на ЭВМ и ограниченно опубликован (освещен) в источниках, хотя С-метод как и ТБМ-метод по известному многочлену синдромов S(z) обеспечивает решение уравнения Падэ над полем Галуа. Это уравнение сформировано для многочлена локаторов ошибок σ(z) и многочлена ω(z), в теории кодирования называется ключевым уравнением Падэ:

Решением ключевого уравнения является совокупность корней многочлена σ(z), и соответственно локаторов , т.е. позиции ошибок. Значения (величины) ошибок определяются из формулы Форни в виде

где и — значения многочленов σ(z) и ω(z) в точке , обратной корню многочлена σ(z);
i — позиция ошибки; — формальная производная многочлена σ(z) по z;

Формальная производная многочлена в конечном поле

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

– это элементы поля, i = 1(1)n

Элементы поля. Задан код над вещественным полем GF(2 4 ). Производная по z имеет вид:

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

Производная по аналогии определяется соотношением:

где ((i)) = 1+1+. +1, (i) раз, суммируемых по правилам конечного поля: знак + обозначает операцию «суммировать столько-то раз», т.е. элемент повторить 2 раза, элемент повторить 3 раза, элемент повторить n раз.

Ясно, что эта операция не совпадает с операции умножения в конечном поле. В частности, в полях GF(2 r ) сумма четного числа одинаковых слагаемых берется по mod2 и обнуляется, а нечетного – равна самому слагаемому без изменений. Следовательно, в поле GF(2 r ) производная получает вид

вторая и старшие четные производные в этом поле равны нулю.

Из алгебры известно, если многочлен имеет кратные корни (кратность р ), то производная многочлена будет иметь этот же корень, но с кратностью р-1. Если р = 1, то f(z) и f ‘(z) не имеет общего корня. Следовательно, если многочлен и его производная имеют общий делитель, то существует кратный корень. Все корни производной f ‘(z) эти корни кратные в f(z).

Метод решения ключевого уравнения

ТМБ (Тренча-Берлекэмпа-Месси) — метод решения ключевого уравнения. Итеративный алгоритм обеспечивает определение многочленов σ(z) и ω(z), и решение уравнения Падэ (ключевого).

Исходные данные: коэффициенты многочлена степени n-1.
Цель. Определение в явном (аналитическом) виде многочленов σ(z) и ω(z).

В алгоритме используются обозначения: j — номер шага, — степень многочлена, — разложение многочлена по степеням и — промежуточные переменные и функции на j-м шаге алгоритма;

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

Пример 4. Выполнение итеративного алгоритма для вектора
S=(8,13,7,13,15,15). Определяются многочлены и .

Таблица 2 – Расчет многочленов локаторов ошибок

Итак , =7z+8.

Многочлен локаторов ошибок σ(z) над полем GF(2 4 ) с неприводимым многочленом p(x) = x 4 + x + 1 имеет корни

и , в этом легко убедиться непосредственной проверкой, т.е. и 13=4^$» data-tex=»inline»/>. Подстановка корней в
=
=;
=
=.

Взяв формальную производную от σ(z), получаем σ_2(z) =2·14+13 =13, так как 14z берется в сумме 2 раза и по mod 2 обращается в нуль.

С использованием формулы Форни найдем выражения для расчета величин ошибок .

Подстановкой значений i = 3 и i = 10 позиций в последнее выражение
находим

= =8$» data-tex=»inline»/>;
= =12$» data-tex=»inline»/>.

Архитектура построения программного комплекса

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

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

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

На каждом этапе работы комплекса предоставляется возможность наглядного представления промежуточных результатов работы.

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

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

Схема функционирования программного комплекса

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

В рамках данного интерфейса должны реализовываться следующие функциональные задачи:

Загрузка исходного сообщения;
Преобразование сообщения в дамп;
Кодирование сообщения;
Моделирование перехваченного сообщения
Построение спектров полученных кодовых слов с целью анализа их визуального представления;
Вывод на экран параметров кода.

Описание работы программного комплекса

При запуске исполняемого файла программы на экране появляется окно представленное на рисунке 2, в котором отображён основной интерфейс программы.

На вход программы подается файл, который нужно передать по каналу связи. Для его передачи по реальным каналам связи требуется кодирование – добавление к нему проверочных символов, необходимых для однозначного декодирования слова на источнике-получателе. Для начала работы комплекса необходимо с помощью кнопки “Загрузить файл” выбрать нужный текстовый файл. Его содержимое будет отображено в нижнем поле главного окна программы.

Двоичное представление сообщения будет представлено в соответствующем поле, двоичное представление информационных слов – в поле “Двоичное представление информационных слов”.

Число бит исходного сообщения и общее число слов в нем отображаются в полях “Количество бит в передаваемом сообщении” и “Количество слов в передаваемом сообщении”.

Сформированные информационные и кодовые слова отображаются в таблицах в правой части основного окна программы.

Окно программы с промежуточными результатами представлено на рисунке 3.

Рисунок 3 – Промежуточное представление результатов работы программного комплекса

Рисунок 4. Результаты загрузки файла сообщения

Рисунок 5. Результаты кодирования файла

Рисунок 6. Вывод сообщения с внесенными в него ошибками.

Рисунок 7. Вывод результатов декодирования и сообщения с внесенными в него ошибками

Рисунок 8. Вывод декодированного сообщения.

Заключение

АНБ США является главным оператором глобальной системы перехвата «Эшелон». «Эшелон» располагает разветвлённой инфраструктурой, включающей в себя станции наземного слежения, расположенные по всему миру. Отслеживаются практически все мировые информационные потоки.

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

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

Видео:Векторы. Метод координат. Вебинар | МатематикаСкачать

Найти кодовые векторы по информационным блокам

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

Коды, у которых все кодовые комбинации разрешены, называются простыми или равнодоступными и являются полностью безызбыточными. Безызбыточные коды обладают большой «чувствительностью» к помехам. Внесение избыточности при использовании помехоустойчивых кодов связано с увеличением n – числа разрядов кодовой комбинации. Таким образом, все множество комбинаций можно разбить на два подмножества: подмножество разрешенных комбинаций, обладающих определенными признаками, и подмножество запрещенных комбинаций, этими признаками не обладающих.

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

Первые работы по корректирующим кодам принадлежат Хеммингу, который ввел понятие минимального кодового расстояния dmin и предложил код, позволяющий однозначно указать ту позицию в кодовой комбинации, где произошла ошибка. К информационным элементам k в коде Хемминга добавляется m проверочных элементов для автоматического определения местоположения ошибочного символа. Таким образом, общая длина кодовой комбинации составляет: n = k + m.

Видео:Единичный векторСкачать

Метричное представление n,k-кодов

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

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

К основным характеристикам корректирующих кодов относятся:

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

Для блочных двоичных кодов, с числом символов в блоках, равным n, общее число возможных кодовых комбинаций определяется значением

Число разрешенных кодовых комбинаций при наличии k информационных разрядов в первичном коде:

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

а с учетом отношение будет

где m – число избыточных (проверочных) разрядов в блочном коде.

Избыточностью корректирующего кода называют величину

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

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

Если число ошибок, которые нужно обнаружить или исправить, значительно, то необходимо иметь код с большим числом проверочных символов. Чтобы при этом скорость передачи оставалась достаточно высокой, необходимо в каждом кодовом блоке одновременно увеличивать как общее число символов, так и число информационных символов.

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

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

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

Количество разрядов (символов), которыми отличаются две кодовые комбинации, можно принять за кодовое расстояние между ними. Для определения этого расстояния нужно сложить две кодовые комбинации «по модулю 2» и подсчитать число единиц в полученной сумме. Например, две кодовые комбинации xi = 01011 и xj = 10010 имеют расстояние d(xi,xj) , равное 3, так как:

Здесь под операцией &#8853 понимается сложение «по модулю 2».

Заметим, что кодовое расстояние d(xi,x0) между комбинацией xi и нулевой x0 = 00. 0 называют весом W комбинации xi, т.е. вес xi равен числу «1» в ней.

Расстояние между различными комбинациями некоторого конкретного кода могут существенно отличаться. Так, в частности, в безызбыточном первичном натуральном коде n = k это расстояние для различных комбинаций может изменяться от единицы до величины n, равной разрядности кода. Особую важность для характеристики корректирующих свойств кода имеет минимальное кодовое расстояние dmin, определяемое при попарном сравнении всех кодовых комбинаций, которое называют расстоянием Хемминга.

В безызбыточном коде все комбинации являются разрешенными и его минимальное кодовое расстояние равно единице – dmin=1. Поэтому достаточно исказиться одному символу, чтобы вместо переданной комбинации была принята другая разрешенная комбинация. Чтобы код обладал корректирующими свойствами, необходимо ввести в него некоторую избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешенными комбинациями не менее двух – dmin &#8805 2..

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

Число обнаруживаемых или исправляемых ошибок

При применении двоичных кодов учитывают только дискретные искажения, при которых единица переходит в нуль («1» &#8594 «0») или нуль переходит в единицу («0» &#8594 «1»). Переход «1» &#8594 «0» или «0» &#8594 «1» только в одном элементе кодовой комбинации называют единичной ошибкой (единичным искажением). В общем случае под кратностью ошибки подразумевают число позиций кодовой комбинации, на которых под действием помехи одни символы оказались замененными на другие. Возможны двукратные (g = 2) и многократные (g > 2) искажения элементов в кодовой комбинации в пределах 0 &#8804 g &#8804 n.

Минимальное кодовое расстояние является основным параметром, характеризующим корректирующие способности данного кода. Если код используется только для обнаружения ошибок кратностью g0, то необходимо и достаточно, чтобы минимальное кодовое расстояние было равно dmin &#8805 g0 + 1.

В этом случае никакая комбинация из go ошибок не может перевести одну разрешенную кодовую комбинацию в другую разрешенную. Таким образом, условие обнаружения всех ошибок кратностью g0 можно записать

Чтобы можно было исправить все ошибки кратностью gu и менее, необходимо иметь минимальное расстояние, удовлетворяющее условию dmin &#8805 2gu

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

Из и следует, что если код исправляет все ошибки кратностью gu, то число ошибок, которые он может обнаружить, равно go = 2gu. Следует отметить, что эти соотношения устанавливают лишь гарантированное минимальное число обнаруживаемых или исправляемых ошибок при заданном dmin и не ограничивают возможность обнаружения ошибок большей кратности. Например, простейший код с проверкой на четность с dmin = 2 позволяет обнаруживать не только одиночные ошибки, но и любое нечетное число ошибок в пределах go 3 = 8). Нулевой синдром (000) указывает на то, что ошибки при приеме отсутствуют или не обнаружены. Всякому ненулевому синдрому соответствует определенная конфигурация ошибок, которая и исправляется. Классические коды Хемминга имеют число синдромов, точно равное их необходимому числу (что позволяет исправить все однократные ошибки в любом информативном и проверочном символах) и включают один нулевой синдром. Такие коды называются плотноупакованными.

Усеченные коды являются неплотноупакованными, так как число синдромов у них превышает необходимое. Так, в коде (9,5) при четырех проверочных символах число синдромов будет равно 2 4 =16, в то время как необходимо всего 10. Лишние 6 синдромов свидетельствуют о неполной упаковке кода (9,5).

Рис. 2 Декодер для (7, 4)-кода Хемминга

Для рассматриваемого кода (7,4) в табл. 2 представлены ненулевые синдромы и соответствующие конфигурации ошибок.

Таким образом, (7,4)-код позволяет исправить все одиночные ошибки. Простая проверка показывает, что каждая из ошибок имеет свой единственный синдром. При этом возможно создание такого цифрового корректора ошибок (дешифратора синдрома), который по соответствующему синдрому исправляет соответствующий символ в принятой кодовой группе. После внесения исправления проверочные символы ri можно на выход декодера (рис. 2) не выводить. Две или более ошибок превышают возможности корректирующего кода Хемминга, и декодер будет ошибаться. Это означает, что он будет вносить неправильные исправления и выдавать искаженные информационные символы.

Идея построения подобного корректирующего кода, естественно, не меняется при перестановке позиций символов в кодовых словах. Все такие варианты также называются (7,4)- кодами Хемминга.

Видео:Найдите разложение вектора по векторам (базису)Скачать

Циклические коды

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

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

Для определения неприводимых многочленов раскладывают на простые множители бином х n -1. Так, для n = 7 это разложение имеет вид:

(x 7 )=(x-1)(x 3 +x 2 )(x 3 +x-1)

Каждый из полученных множителей разложения может применяться для построения корректирующего кода.

Неприводимый полином g(x) называют задающим, образующим или порождающим для корректирующего кода. Длина n (число разрядов) создаваемого кода произвольна. Кодовая последовательность (комбинация) корректирующего кода состоит из к информационных разрядов и n — к контрольных (проверочных) разрядов. Степень порождающего полинома r = n — к равна количеству неинформационных контрольных разрядов.

Если из сделанного выше разложения (при n = 7) взять полипом (х — 1), для которого r=1, то k=n-r=7-1=6. Соответствующий этому полиному код используется для контроля на чет/нечет (обнаружение ошибок). Для него минимальное кодовое расстояние D₀ = 2 (одна единица от D₀ — для исходного двоичного кода, вторая единица — за счет контрольного разряда).

Если же взять полином (x 3 +x 2 +1) из указанного разложения, то степень полинома r=3, а k=n-r=7-3=4.

Контрольным разрядам в комбинации для некоторого кода могут быть четко определено место (номера разрядов). Тогда код называют систематическим или разделимым. В противном случае код является неразделимым.

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

1) На основе порождающей (задающей) матрицы G, которая имеет n столбцов, k строк, то есть параметры которой связаны с параметрами комбинаций кода. Порождающую матрицу строят, взяв в качестве ее строк порождающий полином g(x) и (k — 1) его циклических сдвигов:

Пример; Определить порождающую матрицу, если известно, что n=7, k=4, задающий полином g(x)=x 3 +х+1.

Решение: Кодовая комбинация, соответствующая задающему полиному g(x)=x 3 +х+1, имеет вид 1011. Тогда порождающая матрица G_7,4 для кода при n=7, к=4 с учетом того, что k-1=3, имеет вид:

Порождающая матрица содержит k разрешенных кодовых комбинаций. Остальные комбинации кода, количество которых (2 k — k) можно определить суммированием по модулю 2 всевозможных сочетаний строк матрицы G_n,k. Для матрицы, полученной в приведенном выше примере, суммирование по модулю 2 четырех строк 1-2, 1-3, 1-4, 2-3, 2-4, 3-4 дает следующие кодовые комбинации циклического кода:

Другие комбинации искомого корректирующего кода могут быть получены сложением трех комбинаций, например, из сочетания строк 1-3-4, что дает комбинацию 1111111, а также сложением четырех строк 1-2-3-4, что дает комбинацию 1101001 и т.д.

Ряд комбинаций искомого кода может быть получено путем дальнейшего циклического сдвига комбинаций порождающей матрицы, например, 0110001, 1100010, 1000101. Всего для образования искомого циклического кода требуется 2 k =2 4 =16 комбинаций.

2) Умножение исходных двоичных кодовых комбинаций на задающий полином.

Исходными комбинациями являются все k-разрядные двоичные комбинации. Так, например, для исходной комбинации 1111 (при k = 4) умножение ее на задающий полином g(x)=x 3 +х+1=1011 дает 1101001. Полученные на основе двух рассмотренных способов циклические коды не являются разделимыми.

3) Деление на задающий полином.

Для получения разделимого (систематического) циклического кода необходимо разделить многочлен x n-k *h(x), где h(x) — исходная двоичная комбинация, на задающий полином g(x) и прибавить полученный остаток от деления к многочлену x n-k *h(x).

Заметим, что умножение исходной комбинации h(x) на x n-k эквивалентно сдвигу h(x) на (n-к) разрядов влево.

Пример: Требуется определить комбинации циклического разделимого кода, заданного полиномом g(x)=x 3 +х+1=1011 и имеющего общее число разрядов 7, число информационных разрядов 4, число контрольных разрядов (n-k)=3.

Решение: Пусть исходная комбинация h(x)=1100. Умножение ее на x n-k =x 3 =1000 дает x 3 *(x 3 +x 2 )=1100000, то есть эквивалентно сдвигу исходной комбинации на 3 разряда влево. Деление комбинации 1100000 на комбинацию 1011, эквивалентно задающему полиному, дает:

Полученный остаток от деления, содержащий x n-k =3 разряда, прибавляем к полиному, в результате чего получаем искомую комбинацию разделимого циклического кода: 1100010. В ней 4 старших разряда (слева) соответствуют исходной двоичной комбинации, а три младших разряда являются контрольными.

Следует сделать ряд указаний относительно процедуры деления:

1) При делении задающий полином совмещается старшим разрядом со старшим «единичными разрядом делимого.

2) Вместо вычитания по модулю 2 выполняется эквивалентная ему процедура сложения по модулю 2.

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

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

Видео:Как разложить вектор по базису - bezbotvyСкачать

Логический код 4В/5В

Логический код 4В/5В заменяет исходные символы длиной в 4 бита на символы длиной в 5 бит. Так как результирующие символы содержат избыточные биты, то общее количество битовых комбинаций в них больше, чем в исходных. Таким образом, пяти-битовая схема дает 32 (2 5 ) двухразрядных буквенно-цифровых символа, имеющих значение в десятичном коде от 00 до 31. В то время как исходные данные могут содержать только четыре бита или 16 (2 4 ) символов.

Поэтому в результирующем коде можно подобрать 16 таких комбинаций, которые не содержат большого количества нулей, а остальные считать запрещенными кодами (code violation). В этом случае длинные последовательности нулей прерываются, и код становится самосинхронизирующимся для любых передаваемых данных. Исчезает также постоянная составляющая, а значит, еще более сужается спектр сигнала. Но этот метод снижает полезную пропускную способность линии, так как избыточные единицы пользовательской информации не несут, и только «занимают эфирное время». Избыточные коды позволяют приемнику распознавать искаженные биты. Если приемник принимает запрещенный код, значит, на линии произошло искажение сигнала.

Итак, рассмотрим работу логического кода 4В/5В. Преобразованный сигнал имеет 16 значений для передачи информации и 16 избыточных значений. В декодере приемника пять битов расшифровываются как информационные и служебные сигналы.

Для служебных сигналов отведены девять символов, семь символов — исключены.

Исключены комбинации, имеющие более трех нулей (01 — 00001, 02 — 00010, 03 — 00011, 08 — 01000, 16 — 10000). Такие сигналы интерпретируются символом V и командой приемника VIOLATION — сбой. Команда означает наличие ошибки из-за высокого уровня помех или сбоя передатчика. Единственная комбинация из пяти нулей (00 — 00000) относится к служебным сигналам, означает символ Q и имеет статус QUIET — отсутствие сигнала в линии.

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

Цена за эти достоинства при таком способе кодирования данных — снижение скорости передачи полезной информации. К примеру, В результате добавления одного избыточного бита на четыре информационных, эффективность использования полосы частот в протоколах с кодом MLT-3 и кодированием данных 4B/5B уменьшается соответственно на 25%.

Схема кодирования 4В/5В представлена в таблице.

Итак, соответственно этой таблице формируется код 4В/5В, затем передается по линии с помощью физического кодирования по одному из методов потенциального кодирования, чувствительному только к длинным последовательностям нулей — например, в помощью цифрового кода NRZI.

Символы кода 4В/5В длиной 5 бит гарантируют, что при любом их сочетании на линии не могут встретиться более трех нулей подряд.

Буква ^ В в названии кода означает, что элементарный сигнал имеет 2 состояния — от английского binary — двоичный. Имеются также коды и с тремя состояниями сигнала, например, в коде 8В/6Т для кодирования 8 бит исходной информации используется код из 6 сигналов, каждый из которых имеет три состояния. Избыточность кода 8В/6Т выше, чем кода 4В/5В, так как на 256 исходных кодов приходится 36=729 результирующих символов.

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

Единственное требование — для обеспечения заданной пропускной способности линии передатчик, использующий избыточный код, должен работать с повышенной тактовой частотой. Так, для передачи кодов 4В/5В со скоростью 100 Мб/с передатчик должен работать с тактовой частотой 125 МГц. При этом спектр сигнала на линии расширяется по сравнению со случаем, когда по линии передается чистый, не избыточный код. Тем не менее, спектр избыточного потенциального кода оказывается уже спектра манчестерского кода, что оправдывает дополнительный этап логического кодирования, а также работу приемника и передатчика на повышенной тактовой частоте.

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

Например, для передачи данных по линии с пропускной способностью 100М бит/с и полосой пропускания 100 МГц, кодом NRZI необходимы частоты 25 — 50 МГц, это без кодирования 4В/5В. А если применить для NRZI еще и кодирование 4В/5В, то теперь полоса частот расширится от 31,25 до 62,5 МГц. Но тем не менее, этот диапазон еще «влазит» в полосу пропускания линии. А для манчестерского кода без применения всякого дополнительного кодирования необходимы частоты от 50 до 100 МГц, и это частоты основного сигнала, но они уже не будут пропускаться линией на 100 МГц.

Видео:Собственные векторы и собственные значения матрицыСкачать

Скрэмблирование

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

Устройства, или блоки, выполняющие такую операцию, называются скрэмблерами (scramble — свалка, беспорядочная сборка) .

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

Избыточные биты при этом по линии не передаются.

Суть скремблирования заключается просто в побитном изменении проходящего через систему потока данных. Практически единственной операцией, используемой в скремблерах является XOR — «побитное исключающее ИЛИ», или еще говорят — сложение по модулю 2. При сложении двух единиц исключающим ИЛИ отбрасывается старшая единица и результат записывается — 0.

Метод скрэмблирования очень прост. Сначала придумывают скрэмблер. Другими словами придумывают по какому соотношению перемешивать биты в исходной последовательности с помощью «исключающего ИЛИ». Затем согласно этому соотношению из текущей последовательности бит выбираются значения определенных разрядов и складываются по XOR между собой. При этом все разряды сдвигаются на 1 бит, а только что полученное значение («0» или «1») помещается в освободившийся самый младший разряд. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом. Затем эта последовательность выдается в линию, где с помощью методов физического кодирования передается к узлу-получателю, на входе которого эта последовательность дескрэмблируется на основе обратного отношения.

Например, скрэмблер может реализовывать следующее соотношение:

где Bi — двоичная цифра результирующего кода, полученная на i-м такте работы скрэмблера, A_i — двоичная цифра исходного кода, поступающая на i-м такте на вход скрэмблера, B_i-3 и B_i-5 — двоичные цифры результирующего кода, полученные на предыдущих тактах работы скрэмблера, соответственно на 3 и на 5 тактов ранее текущего такта, ⊕ — операция исключающего ИЛИ (сложение по модулю 2).

Теперь давайте, определим закодированную последовательность, например, для такой исходной последовательности 110110000001.

Скрэмблер, определенный выше даст следующий результирующий код:

B₁=А₁=1 (первые три цифры результирующего кода будут совпадать с исходным, так как еще нет нужных предыдущих цифр)

Таким образом, на выходе скрэмблера появится последовательность 110001101111. В которой нет последовательности из шести нулей, п рисутствовавшей в исходном коде.

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

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

Главная проблема кодирования на основе скремблеров — синхронизация передающего (кодирующего) и принимающего (декодирующего) устройств. При пропуске или ошибочном вставлении хотя бы одного бита вся передаваемая информация необратимо теряется. Поэтому, в системах кодирования на основе скремблеров очень большое внимание уделяется методам синхронизации.

На практике для этих целей обычно применяется комбинация двух методов:

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

б) использование высокоточных генераторов временных импульсов, что позволяет в моменты потери синхронизации производить декодирование принимаемых битов информации «по памяти» без синхронизации.

Существуют и более простые методы борьбы с последовательностями единиц, также относимые к классу скрэмблирования.

Для улучшения кода ^ Bipolar AMI используются два метода, основанные на искусственном искажении последовательности нулей запрещенными символами.

Рис. 3 Коды B8ZS и HDB3

На этом рисунке показано использование метода ^ B8ZS (Bipolar with 8-Zeros Substitution) и метода HDB3 (High-Density Bipolar 3-Zeros) для корректировки кода AMI. Исходный код состоит из двух длинных последовательностей нулей (8- в первом случае и 5 во втором).

Код B8ZS исправляет только последовательности, состоящие из 8 нулей. Для этого он после первых трех нулей вместо оставшихся пяти нулей вставляет пять цифр: V-1*-0-V-1*. V здесь обозначает сигнал единицы, запрещенной для данного такта полярности, то есть сигнал, не изменяющий полярность предыдущей единицы, 1* — сигнал единицы корректной полярности, а знак звездочки отмечает тот факт, что в исходном коде в этом такте была не единица, а ноль. В результате на 8 тактах приемник наблюдает 2 искажения — очень маловероятно, что это случилось из-за шума на линии или других сбоев передачи. Поэтому приемник считает такие нарушения кодировкой 8 последовательных нулей и после приема заменяет их на исходные 8 нулей.

Код B8ZS построен так, что его постоянная составляющая равна нулю при любых последовательностях двоичных цифр.

Код HDB3 исправляет любые 4 подряд идущих нуля в исходной последовательности. Правила формирования кода HDB3 более сложные, чем кода B8ZS. Каждые четыре нуля заменяются четырьмя сигналами, в которых имеется один сигнал V. Для подавления постоянной составляющей полярность сигнала V чередуется при последовательных заменах.

Кроме того, для замены используются два образца четырехтактовых кодов. Если перед заменой исходный код содержал нечетное число единиц, то используется последовательность 000V, а если число единиц было четным — последовательность 1*00V.

Таким образом, применение логическое кодирование совместно с потенциальным кодированием дает следующие преимущества:

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

Видео:Доказать, что векторы a, b, c образуют базис и найти координаты вектора d в этом базисеСкачать

Линейные блочные коды

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

Кодер служит для преобразования поступающей от источника сообщений последовательности из k информационных символов в последовательность из n cимволов кодовых комбинаций (или кодовых слов). Совокупность кодовых слов образует код.

Множество символов, из которых составляется кодовое слово, называется алфавитом кода, а число различных символов в алфавите – основанием кода. В дальнейшем вследствие их простоты и наибольшего распространения рассматриваются главным образом двоичные коды, алфавит которых содержит два символа: 0 и 1.

Рис. 4 Система передачи дискретных сообщений

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

С математической точки зрения кодер осуществляет отображение множества из 2 k элементов (двоичных информационных последовательностей) в множество, состоящее из 2 n элементов (двоичных последовательностей длины n). Для практики интересны такие отображения, в результате которых получаются коды, обладающие способностью исправлять часть ошибок и допускающие простую техническую реализацию кодирующих и декодирующих устройств.

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

Наиболее распространено предположение о действии в канале аддитивной помехи. Пусть S=(s₁,s₂. s_n) и Y=(y₁,y₂. y_n) соответственно входная и выходная последовательности двоичных символов. Помехой или вектором ошибки называется последовательность из n символов E=(e₁,e₂. e_n), которую надо поразрядно сложить с переданной последовательностью, чтобы получить принятую:

Таким образом, компонента вектора ошибки e_i=0 указывает на то, что 2-й символ принят правильно (y_i=s_i), а компонента e_i=1 указывает на ошибку при приеме (y_i≠s_i).Поэтому важной характеристикой вектора ошибки является число q ненулевых компонентов, которое называется весом или кратностью ошибки. Кратность ошибки – дискретная случайная величина, принимающая целочисленные значения от 0 до n.

Классификация двоичных каналов ведется по виду распределения случайного вектора E. Основные результаты теории кодирования получены в предположении, что вероятность ошибки в одном символе не зависит ни от его номера в последовательности, ни от его значения. Такой канал называется стационарным и симметричным. В этом канале передаваемые символы искажаются с одинаковой вероятностью P, т.е. P(e_i=1)=P, i=1,2. n.

Для симметричного стационарного канала распределение вероятностей векторов ошибки кратности q является биноминальным:

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

Декодирующее устройство (декодер) предназначено оценить по принятой последовательности Y=(y₁,y₂. y_n) значения информационных символов A ‘ =(a ‘ ₁,a ‘ ₂. a ‘ _k,). Из-за действия помех возможны неправильные решения. Процедура декодирования включает решение двух задач: оценивание переданного кодового слова и формирование оценок информационных символов.

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

Наибольшую трудность представляет первая задача декодирования. При равновероятных информационных последовательностях ее оптимальное решение дает метод максимального правдоподобия. Функция правдоподобия как вероятность получения данного вектора Y при передаче кодовых слов S_i, i=1,2. 2 k на основании Y=S+E определяется вероятностями появления векторов ошибок:

Очевидно, вероятность P(Y/S_i) максимальна при минимальном q_i. На основании принципа максимального правдоподобия оценкой S ‘ является кодовое слово, искажение которого для превращения его в принятое слово Y имеет минимальный вес, т. е. в симметричном канале является наиболее вероятным (НВ):

Если несколько векторов ошибок E_i имеют равные минимальные веса, то наивероятнейшая ошибка E_HB определяется случайным выбором среди них.

В качестве расстояния между двумя кодовыми комбинациями принимают так называемое расстояние Хэмминга, которое численно равно количеству символов, в которых одна комбинация отлична от другой, т.е. весу (числу ненулевых компонентов) разностного вектора. Расстояние Хэмминга между принятой последовательностью Y и всеми возможными кодовыми словами 5, есть функция весов векторов ошибок E_i:

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

Таким образом, оптимальная процедура декодирования для симметричного канала может быть описана следующей последовательностью операций. По принятому вектору Y определяется вектор ошибки с минимальным весом E_HB, который затем вычитается (в двоичном канале — складывается по модулю 2) из Y:

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

Широко распространены линейные коды, называемые так потому, что их кодовые слова образуют линейное подпространство над конечным полем. Для двоичных кодов естественно использовать поле характеристики p=2. Принадлежность принятой комбинации Y известному подпространству является тем признаком, по которому выносится решение об отсутствии ошибок (E_HB=0).

Так как по данному коду все пространство последовательностей длины n разбивается на смежные классы, то для каждого смежного класса можно заранее определить вектор ошибки минимального веса, называемый лидером смежного класса. Тогда задача декодера состоит в определении номера смежного класса, которому принадлежит Y, и формировании лидера этого класса.