Исправьте ошибки в приведенном фрагменте программного кода program z1

Исправление кратных ошибок при кодировании сообщений

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

Теоретические положения

Идея использования организованной избыточности в сообщениях привела Р. Хемминга к построению корректирующего кода описанного здесь. Линейный корректирующий (n, k)-код характеризуется проверочной (m? n) матрицей H. Требования к матрице просты: число строк совпадает с числом проверочных символов, ее столбцы должны быть отличны от нулевого и все различны. Более того, значения столбцов описывают номера позиций, занимаемых в кодовом слове символами слова, являющимися элементами конечного поля.

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

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

Пусть m = 5 и n = 31. Желательно было бы получить (n, k)-код, исправляющий двойные ошибки, с проверочной матрицей Н в виде:

Для обозначенных в матрице функций fj(?) желательно иметь функцию, которая отображала бы множество 5-мерных векторов в себя. Последние 5 строк матрицы будут задавать код Хемминга тогда и только тогда, когда функция f является биекцией (перестановкой).

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

Мы должны научиться складывать, вычитать, умножать и делить двоичные 5-ти мерные векторы, представлять их многочленами степени не выше 4-ой, чтобы находить требуемую функцию fj(?).

Пример 2
00000 <> 0
00010 <> 1
00011 <> х
…

Сумма и разность таких многочленов соответствует сумме и разности векторов:
0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0, знаки ± имеют в двоичном случае совпадающий смысл. Не так с умножением, показатель степени результата умножения может превысить 4.

Необходим метод понижения степеней больше 4.
Он называется (редукцией) построением вычетов по модулю неприводимого многочлена M(x) степени 5; метод состоит в переходе от многочленов произведений к их остаткам от деления на

Символ? читается «сравнимо с».

В общем виде A(x) ?a(x)mod M(x)
Тогда и только тогда, когда существует такой многочлен C(x), что
A(x)= M(x)C(x) +a(x) коэффициенты многочленов приводятся по модулю два:
A(x) ? a(x)mod(2,M(x)).

Важные свойства сравнений

Если а(x) ?А(x)mod M(x) и b(x) ? B(x)mod M(x), то
А(x) ± b(x) ? А(x) ± B(x)mod M(x) и
А(x)·b(x) ? А(x)·B(x)mod M(x).

Более того, если степени многочленов а(х) и А(х) меньше степени М(х), то из формулы
А(x) ? А(x)mod(2,M(x)) следует, что а(x) = А(x).

Различных классов вычетов существует 2 в степени degM(x) – т. е. столько, сколько существует различных многочленов степени, меньшей m, т. е. сколько может быть различных остатков при делении. С делением еще больше сложностей.

Алгоритм деления

Для данных a и M существуют однозначно определенные числа q и A, такие, что а =qM + A, 0 ? A? M,
Для многочленов с коэффициентами из данного поля.

Для данных a(x) и M(x) существуют однозначно определенные многочлены q(x) и A(x), такие, что a(x) = q(x)M(x) + A(x), degA(x) <deg M(x).

Возможность деления многочленов обеспечивается алгоритмом Евклида.

Для чисел пример расширенного НОД описан здесь.

Для заданных a и b существуют такие числа A и B, что aA +bB = (a, b), где (a, b) – НОД чисел a и b.

Для многочленов с коэффициентами из данного поля.

Для заданных a(x) и b(x) существуют такие многочлены A(x) и B(x), что
A(x)A(x) + b(x)B(x) = (a(x), b(x)),

Где (a(x), b(x)) — нормированный общий делитель a(x) и b(x) наибольшей степени.
Если а(х) и М(х) имеют общий делитель d(x) ? 1, то деление на a(x) по mod M(x) не всегда возможно.

Очевидно, что деление на a(x) эквивалентно умножению на A(x).

Так как если (a(x), b(x))= 1 =НОД, то согласно алгоритму Евклида, существуют такие A(x) и B(x), что a(x)A(x) + b(x)B(x) = 1, так, что a(x)A(x) ? 1mod b(x). Проверка того, что двоичный многочлен является неприводимым над полем GF (), выполняется непосредственным делением на всевозможные делители со степенями, меньшими, чем deg M(x).

Переходим к поиску функции для проверочной матрицы H, задающей код с исправлением двойных ошибок с блоковой длиной 31 и скоростью 21/31; 31-21=10 =2t – проверочных символов = 10. Такая функция должна иметь своими корнями номера ошибочных позиций в кодовом слове, т. е. при подстановке в эту функцию номеров позиций, обращает ее в нуль.

Поиск функции

Предположим, что ?1 и ?2 — номера искаженных символов (позиций) слова. Используя двоичную запись чисел ?1 и ?2 можно представить эти номера в виде классов вычетов по модулю M(x) т. е. установить соответствие ?i > ? (i) (x) — двоичные многочлены степени < 5.

Первые 5 проверочных условий определяют ?1 + ?2; второе множество проверочных уравнений должны определять F(?1) + f(?2).

Декодер должен определить ?1 и ?2 по заданной системе:

Какой же должна быть функция F(x)?

Простейшая функция – это умножение на константу F(?)? ??(х)modM(x).

Но тогда ?2 = ??1, т. е. уравнения системы зависимы. Новая пятерка проверочных условий декодеру не даст ничего нового.

Аналогично и функция F(?) = ? + ? не изменяет ситуацию, так как ?2 = ?1.

Эти уравнения также зависимы, так как

Так что при ?1?0 имеем

Значит, ?1 и ?2 удовлетворяют уравнению

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

Так как в поле двоичных многочленов по модулю M(x) данное уравнение имеет точно 2 корня, то декодер всегда сможет найти два нужных локатора.

Более удобно (на практике) оперировать не непосредственно с многочленом, корнями которого являются локаторы ошибок, а с многочленом, корни которого взаимны к локаторам; т. е. являются к ним мультипликативным обратными величинами.

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

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

Первые пять проверок задают сумму номеров ошибок (S1); вторые пять проверок задают сумму кубов номеров ошибок (S3).

Часть 3 – Отладка программы

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

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

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

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

Синтаксические ошибки

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

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

Семантические ошибки

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

Рассмотрим данный пример:

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

3 + 5, заключенные в скобки, дадут желаемый результат, а именно 48.

Ошибки в процессе выполнения

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

Вот хороший пример:

Фрагмент кода выше будет скомпилирован успешно, но Input 25 приведет к ZeroDivisionError. Это ошибка во время выполнения. Другим популярным примером является StackOverflowError или IndexOutofBoundError. Важно то, что вы идентифицируете эти ошибки и узнаете, как с ними бороться.

Существуют ошибки, связанные с тем, как ваш исходный код использует память и пространство на платформе или в среде, в которой он запущен. Они также являются ошибками во время выполнения. Такие ошибки, как OutOfMemoryErrorand и HeapError обычно вызваны тем, что ваш исходный код использует слишком много ресурсов. Хорошее знание Алгоритмов поможет написать код, который лучше использует ресурсы. В этом и заключается отладка программы.

Процесс перезаписи кода для повышения производительности называется Оптимизацией. Менее популярное наименование процесса – Рефакторинг. Поскольку вы тратите больше времени на кодинг, то должны иметь это в виду.

Отладка программы

Вот несколько советов о том, как правильно выполнять отладку:

Двигаемся дальше

Поздравляем! Слово «ошибка» уже привычно для вас, равно как и «отладка программы». В качестве новичка вы можете изучать кодинг по книгам, онлайн-урокам или видео. И даже чужой код вам теперь не страшен

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