Pull to refresh

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

Reading time 17 min
Views 29K

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

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

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

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

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


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

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

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

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

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

Определение. РС-кодом над полем GF(q=рm), с длиной блока n = qm-1, исправляющим t ошибок, является множество всех кодовых слов u(n) над GF(q), для которых 2t последовательных компонентов спектра с номерами $m_0,m_0 +1,...,m_0+2t-1$ равны 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) (modz2t) сравним по модулю z2t с произведением многочлена локаторов ошибок на синдромный многочлен.

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

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

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

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


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

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

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


В таблице П эти корни имеют и степенное представление $α^1=2, α^2=3,...,α^6=7$.


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


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

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

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

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

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

После преобразований получаем несистематическое кодовое слово (вектор) в виде
Q·g = <11, 15, 3, 9, 6, 14, 7, 5, 12, 15, 14, 3, 3, 7, 1>.

При систематическом кодировании сообщение (информационный вектор) представляют многочленом Q(z) в форме Q(z)=q(z)·g(z) + R(z), где степень degR(z)<m = 6. После этого к вектору Q справа приписывается остаток R (всё в десятичном виде). Это делается так.

Многочлен Q сдвигают в сторону старших разрядов на величину m = n — k, что достигается путём умножения Q(z) на Zn — k (в примере Zn — k = Z 6) и выполняют после сдвига деление Q(z)·Zn — k на g(z). В результате находят остаток от деления R(z). Все операции выполняют над полем GF(24)

(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<15> — кодовое слово в систематическом виде. Этот вид явно содержит информационное сообщение в k старших разрядах кодового слова

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

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

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


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

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

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

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

Вычисление синдрома.

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

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

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


Синдромный $S = (S_v,S_{v+1},...,S_{m+v-1})$, где $v∊{0, 1}$ вектор последовательно определяется для каждого из полученных декодером на его входе кодовых слов. При нулевых значениях компонентов вектора синдрома $Sj = 0, j=v,v+1,...,m + v - 1$, декодер считает, что в принятом слове ошибки нет. Если же хотя бы для одного $j≥1,Sj≠0$, то декодер делает вывод о наличии ошибок в кодовом векторе и приступает к их выявлению, что является 1-м шагом работы декодера.

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

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

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

Кодовый вектор с ошибками представлен в виде C(E) =C + E, E– вектор ошибок. Тогда $(C +E)H^t = CH^t + EH^t = 0 + EH^t = S$

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

$S_j = C_0 +α^j(C_1 +α^j(C_2 +...+α^j(C_{n-2} +α^jC_{n-1})...))$

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

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

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


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

$(7+12) →α^6+α^11 =x^3 +x^2 +x^3 +x^2 +x^1 =α^1 = 2,$
$(3 + 8) →α^2+ α^7 =x^2 +x^3 +x^1 + 1 =α^{12}=13.$

Декодер вычисления выполняет по общей формуле для компонентов Sj, j=1(1)m. Здесь (в модели) используем соотношение $S=EH^t$, так как 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.
Относительно кодового слова с длиной $n<q=p^r$, поступающего на вход декодера мы допускаем, что оно искажено ошибками.

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

  • количество искаженных позиций у кодового слова
  • $v≤v_{max}=0.5m$;
  • номера (положение) искаженных позиций в кодовом слове $ ℓ_i: ℓ_i=0(1)n-1$;
  • значения (величины) искажений $e_ℓ; e_ℓ∊GF(2^4)$.

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

Пример 3. (Вычисление компонентов синдромного вектора $S_{<6>}$ )


то в итоге имеем $S_{<6>}=(S_1,S_2,S_3,S_4,S_5,S_6)$ =<8,13,7,13,15,15>

Для дальнейшего рассмотрения введем новые понятия. Величину $x_i = α^{ℓ_i}$будем называть локатором ошибок, здесь искаженный символ кодового слова на позиции $ℓ_i$, α – примитивный элемент поля GF(24).

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

При этом выражения $(1-zx_i)=0 $обращаются в нуль.

$σ(z) = (1-zx_1)(1-zx_2)...(1-zx_v) =σ_vz^v +σ_{v-1}z^{v-1} +...+σ_1z +σ_0$
всегда свободный член уравнения всегда свободный член уравнения $σ_0 =1$.
Степень многочлена локаторов ошибок равна v – количеству ошибок и не превышает величины $v≤v_{max}=0.5m$.

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

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


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

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

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

В уравнение $σ_i$ многочлена локаторов ошибок подставляется значение его корней $z =x_i^{-1}$. При этом многочлен обращается в нуль. Образуется тождество, обе части которого умножаем на $y_ix_i^{j+v}$, получаем:

$y_i(σ_vx_i^{j}+σ_{v-1}x_i^{j+1}+...+σ_1x_i^{j+v-1}+x_i^{j+v})=0,1≤i≤v, 1≤j≤v$.

Таких равенств получаем $v×v =v^2$

Суммируем эти равенства по всем $ i, 1≤i≤v$, при которых эти равенства выполняются. Так как многочлен σ(z) имеет v корней $x_i^{-1}$, раскроем скобки и перенесем коэффициенты $σ_i$ за знак суммы:


В этом равенстве согласно системе нелинейных уравнений, приведенной
ранее, каждая сумма равна одному из компонентов вектора синдрома. Отсюда заключает, что относительно коэффициентов $σ_v, σ_{v-1},...,σ_1$ можно выписать систему уже линейных уравнений.


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


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

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


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

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

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

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

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

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

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

$S(z)σ(z) = ω(z)(mod z^m)$.

Решением ключевого уравнения является совокупность $x_i^{-1}$ корней многочлена σ(z), и соответственно локаторов $x_i =α^{ℓ_i}$, т.е. позиции ошибок. Значения (величины) ошибок $e_i$ определяются из формулы Форни в виде


где $σ_z^{'}(α^{-i})$ и $ ω(α^{-i})$ — значения многочленов σ(z) и ω(z) в точке $z =α^{-i}$, обратной корню многочлена σ(z);
i — позиция ошибки;$σ_z^{'}(z)$ — формальная производная многочлена σ(z) по z;

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


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


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

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


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

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


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

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


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

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

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


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

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

В алгоритме используются обозначения: j — номер шага, $v_j$ — степень многочлена, $σ_j(z) =σ_{ji}z^i +σ_{ji-1}z^{i-1}+...+σ_{j1}z+σ_{j0}$ — разложение многочлена по степеням $z, k_j, L_j, θ_j(z)$ и $ Ω_j(z)$ — промежуточные переменные и функции на j-м шаге алгоритма;

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

Начальные условия:


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

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



Итак $σ_j^←(z)=14z^2+13z+1$, $ω_j^←(z)$=7z+8.

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

$z_1 = α^{-i_1} = 13 = 4^{-1}$ и $z_2 =α^{-i_2} = 6 = 11^{-1}$, в этом легко убедиться непосредственной проверкой, т.е. $i_1= 3, i_2 =10, 13 = α^{12}, 1 =α^{12}α^{3}$ и $α^{12} =α^{-3}=>13=4^{-1}$. Подстановка корней в
$σ(z=13)=14(13)^2+13·13+1=α^{13}(α^{12})^2+(α^{12})^2+α^0= α^{37}+α^{24} +α^{0}$=
=$α^{7}+α^{9}+α^0 =x^3+x+1=0(mod2)$;
$σ(z = 6)=14(6)^2+13·6+1 = α^{13}(α^{5})^2+(α^{5})^2+α^{0}$=
=$α^{8}+α^{2} +α^{0} = x^2 +1+x^2 +1 = 0(mod2)$.

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

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

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

$е_3 = 10α^{15-3}+11 =α^{6}+α^{10}$= =$x^3+x^2+x^2+x+1=x^3+x+1=α^{7}=>8$;
$е_{10} = 10α^{15-10}+11 =α^{9}α^{5}+α^{10}=α^{14}+α^{10}$= =$x^3+x^2+x=α^{11}=>12$.

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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


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


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


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


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

Заключение


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

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

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

Список используемой литературы
  1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986. – 576 с.
  2. Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. – М.: Связь, 1979. – 744 с.
  3. Берлекэмп Э. Алгебраическая теория кодирования. – М.: Мир, 1971. – 478 с.
  4. Габидулин Э.М., Афанасьев В.Б. Кодирование в радиоэлектронике. – М.: Радио и связь, 1986. – 176 с., ил.
  5. Вернер М. Основы кодирования. Учебник для ВУЗов. – М.: Техносфера, 2004. – 288 с.
  6. Трифонов П.В. Адаптивное кодирование в многочастотных системах. Диссертация на соискание ученой степени кандидата технических наук. – СПб: Санкт-Петербургский государственный политехнический университет, 2005. – 147 с.
  7. Фомичев С. М., Абилов А.В. Обзор математических моделей каналов связи и их применение в телекоммуникационных системах. – Ижевск: Ижевский государственный технический университет, 2001. – 60 с.
  8. Касами Т., Токура Н., Ивадари Е., Инагаки Я. Теория кодирования. – М.: Мир, 1978. – 576 с.
  9. Муттер В. М. Основы помехоустойчивой телепередачи информации. – Л.: Энергоатомиздат. Ленинградское отделение, 1990. – 288 с.
  10. Ваулин А. Е., Смирнов С.И. «Моделирование помехозащищенного канала передачи сообщения в системе связи»/Сборник алгоритмов и программ типовых задач. Вып.26. под редакцией ктн доц. И.А. Кудряшова –. СПб.: ВКА им А.Ф. Можайского, 2007. – стр. 121-130.
  11. Карпушев С.И Конспект лекций по алгебре (часть 2. Абстрактная алгебра). – ВИКУ им. А. Ф. Можайского, 2002. – 97 с.
  12. Зайцев И. Е. Методика определения параметров помехоустойчивого каскадного кодирования. – Л.: ВИКИ, 1987 – 120 с.
Tags:
Hubs:
+12
Comments 7
Comments Comments 7

Articles