Помехозащищенный (корректирующий) код Файра

Размещено на http://www.allbest.ru/

Содержание

Введение

Основные определения и теоремы

Задание 1. Определение цикличного кода, по порождающей или проверочной матрице

Задание 2. Построение порождающего и проверочного многочленов по циклическому коду. Методы построения циклических кодов

Задание 3. Постановка задачи. Код Файра. Построение кода Файра. Спецификация на программные модули

Результаты тестирования

Список литературы

Текст программных модулей

Введение

цикличный код файр матрица

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

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

Два научных направления призваны сыграть особую роль в научно-техническом прогрессе. Это - теория систем и теория информации. Особенность указанных научных направлений состоит в их всеобщности. Действительно, теория систем и теория информации имеют прямое отношение ко всем другим наукам, к явлениям любой физической природы и ко всем видам деятельности человека. Достаточно привести такое категорическое утверждение по этому поводу: “Информация есть всеобщее свойство материи и мера организация систем”. В ходе научно-технической революции наука об информации развивалась как дисциплина, имеющая ряд направлений. Деятельность людей связана с переработкой и использованием материалов, энергии и информации. Соответственно развивались научные технические дисциплины, отражающие вопросы технологии, энергетики и информатики. Информационная техника является сравнительно новой отраслью, получившее наибольшее развитие на этапе развития и применения электронных вычислительных машин (ЭВМ) и автоматизированных систем управления (АСУ). В ряду новых дисциплин (исследование операций, системотехника, административное управление) информационные наука и техника занимают одно из базовых положений. К информационной технике относятся средства, служащие для восприятия, подготовки, передачи, переработки, хранения и представления какой-либо информации, получаемой от человека, природы, машины, вообще от какого-либо объекта наблюдения и управления. Комплексное применение этих средств приводит к созданию больших и сложных информационных систем. С передачей и обработкой информации связаны действия любого автоматического устройства, поведение живого существа, творческая деятельность человека, развитие науки и техники, экономические и социальные преобразования в обществе и сама жизнь. Если материал (вещество) и энергия сравнительно полно изучены, то законы получения, преобразования и использования информации еще являются не известной областью, таящей в себе много неожиданных проявлений.

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

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

Основные определения и теоремы

Определение 1. Линейным кодированием будем называть инъективное линейное отображение ц: F> F, где k?n.

Определение 2. Пусть ц: F > F, где k?n - линейное кодирование. Тогда образ ц называется линейным (n,k) - кодом.

Пусть F, как и прежде, есть n-мерное векторное пространство над Fq с обычными операциями сложения и умножения их на элементы из Fq. Отображение

Z: F> F, (а0, а1, … ,аn-1) > (аn-1, а0, a1, … ,аn-2)

линейно и называется циклическим сдвигом.

Определение 3. Пусть H - (n-k)n - матрица ранга n-k с элементами из Fq. Множество С всех n-мерных векторов х над Fq, удовлетворяющих равенству HxT=0, называется линейным кодом над Fq, блоковой длины n. Матрица Н называется проверочной матрицей кода С.

Если Н имеет вид (А,In-k), то первые k символов кодового слова х называются информационными, а последние n-k - проверочными символами. Код С называют тогда систематическим линейным (n,k) - кодом.

Определение 4. Матрица G=(Ik,-AT) называется канонической порождающей матрицей (или матрицей кодирования) линейного (n,k) - кода с проверочной матрицей H=(A,In-k).

В этом случае имеем GHT=0.

Также код может иметь несколько проверочных матриц.

Определение 5. Подпространство С из Fq называется циклическим кодом, если

Z(v) C для всех v C, т.е.

v=(v0,v1, … ,vn-1) C > (vn-1,v0, … ,vn-2) C ,для v F.

Задание №1. Определение цикличного кода, по порождающей или проверочной матрице

Пример 1. Пусть код С F определяется порождающей матрицей

=

Покажем, что С цикличен. Каждое кодовое слово из С является линейной комбинацией линейно независимых векторов g(1), g(2), g(3). C цикличен тогда и только тогда, когда Z(g(i)) C для 1=1, 2, 3. Имеем

Z(g(1))= g(2),

Z(g(2))= g(3),

Z(g(3))= g(1)+ g(2).

Теорема 1. Линейный код С Vn цикличен тогда и только тогда, когда С - идеал в Vn.

Доказательство: Пусть С цикличен и f=?aixi Fq[x]. Тогда для v C имеем f*v=?ai(xiv)= ?aiZi(v) C и кроме того, С - подпространство в Vn. Ясно, что С есть главный идеал (g), где g - ненулевой многочлен из С наименьшей степени.

Обратно, пусть С=(g) и v C. Так как Z(v)=xv C, мы видим, что код цикличен.

Замечание и определение 1. Многочлен g, такой, что С=(g) в доказательстве теоремы 1, можно считать нормированным. Кроме того, g|xn-1. В самом деле, если d=НОД(g,xn-1), то d=fg+h(xn-1) для некоторых f, g Fq[x], т.е. d=fg C. Но g имеет наименьшую неотрицательную степень в C, т.е. g=d|(xn-1). Таким образом, многочлен g определён однозначно и называется порождающим многочленом кода С. Элементы из С называются кодовыми словами, кодовыми многочленами или кодовыми векторами.

Замечание 2. Пусть g=g0+g1x+…+gmxm, g|(xn-1) и deg g = m<n. Положим k=n-m. Тогда линейный (n,k) - код С, порожденный матрицей.

,

цикличен. В самом деле, достаточно убедится, что циклический сдвиг нижней строки в G есть кодовое слово. Пусть xn-1=gh, где h=h0+h1x+…+hkxk. Тогда gh0, т.е.

xkg-h(h0g+h1(xg)+…+hk-1(xk-1g)) - линейная комбинация строк из G, откуда xkg C. Очевидно, С=(g).

Программа №1 написана на Visual Basic. Данная программа по порождающей, либо по проверочной матрице линейного кода, определяет является ли код циклическим. Если дана порождающая матрица(G), то строится проверочная матрица(H), или по проверочной матрице строится порождающая матрица, делается проверка GHT=0. Вычисляется с помощью по последней строчке, можно ли получить остальные строчки с помощью циклических сдвигов, тем самым определяя является ли линейный код циклическим. Листинг программы в приложении №1.

Задание 2. Построение порождающего и проверочного многочленов по циклическому коду. Методы построения циклических кодов

Если xn-1=g1…gt - полное разложение xn-1 на неприводимые многочлены над Fq, то циклические коды (gi), порожденные многочленами gi, называется максимальными циклическими кодами. Максимальный циклический код является максимальным идеалом в факторкольце Fq[x]/(xn-1). Любой циклический код в Fq можно получить, выбирая в качестве порождающего многочлена главного идеала один из 2r делителей многочлена xn-1. Многие из этих кодов будут эквивалентны.

Если g - порождающий многочлен циклического кода С, то g|(xn-1). Поэтому

h=(xn-1)/g - также порождающий многочлен некоторого циклического кода. Если deg g = m= n-k, то deg h = k.

Определение 6. Пусть g - порождающий многочлен циклического кода С. Тогда многочлен h = (xn-1)/g называется проверочным многочленом кода C. Будем писать h = , hk0.

Сформулируем некоторые результаты об идеалах, заметив, что в кольце Vn=Fq[x]/(xn-1) все идеалы - главные. Пусть J1 и J2 - идеалы в Vn. Пересечение J1J2 -также идеал, хотя объединение J1 и J2 идеалом, вообще говоря, не будет. Идеал J1+J2 - наименьший идеал, содержащий J1 и J2. Произведение J1J2 := {} - также идеал в Vn. Пусть Ji - идеал в Vn, порожденный многочленом gi. Тогда

(I) J1+J2 порождается НОД(g1, g2);

(II) J1J2 порождается НОД(g1, g2);

(III) J1J2 порождается НОД(g1, g2, xn-1).

Пусть (xn-1)=g1…gt - разложение xn-1 на различные неприводимые многочлены над Fq. (xn-1)/gi - порождающий многочлен так называемого минимального кода, а gi - порождающий многочлен соответствующего максимального кода. Коды, порожденные

(xn-1)/gi, называются также неприводимыми циклическими кодами.

Пример 2. Пусть n=7, q=2 и x7-1=(x+1)(x3+x+1)(x3+x2+1). Многочлен g= x3+x2+1 порождает циклический (7, 4) - код с проверочным многочленом h=x4+x3+x2+1. Каноническая порождающая матрица состоит из строк g(j) при j=3, 4, 5, 6. Поэтому

и

Кодирование. Пусть a=a0…ak-1F- сообщение из k=n-m символов. Тогда а, отождествляемое с многочленом в F[x], кодируется как ag. Отображение , аag, линейно и инъективно, причем ag C=(g).

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

Пример 3. Найти порождающий многочлен линейного циклического кода длины n=15, который осуществляет кодирование сообщений длины k = 7. Затем кодировать сообщение [0110110].

Если нам нужен порождающий многочлен для кода длины 15 при длине сообщения 7, то нужно найти делитель x15 + 1 степени 15 - 7 = 8.

Многочлен x15 + 1 разлагается на множители

x15 + 1 = (1 + x)(1 + x + x2)(1 + x + x2 + x3 + x4)(1 + x + x4)(1 + x3 + x4), поэтому можно взять g(x) = (1 + x + x2 + x3 + x4)(1 + x + x4) = 1 + x4 + x6 + x7 + x8. Используя этот многочлен, как порождающий многочлен мы строим код с минимальным расстоянием 5, который исправляет 2 ошибки. Найдя порождающий многочлен, мы можем кодировать сообщение [0110110]. В полиномиальной интерпретации вектору [0110110] соответствует x + x2 + x4 + x5. Умножим его на порождающий многочлен g(x).

(x + x2 + x4 + x5)(1 + x4 + x6 + x7 + x8) = x + x2 + x4 + x6 + x7 + x8 + x9 + x13

Соответствующее кодовое слово [011010111100010]. Итак, сообщение [0110110] кодировано в слово [011010111100010].

Процедура декодирования циклического кода следующая [3].

1. Найти синдромный многочлен s(x) = r(x)(mod g(x)), где r(x) полученное слово.

2. Для каждого i >= 0, вычислять si(x) = xis(x)(mod g(x)) до тех пор, пока не будет найден, sj такой, что для него (вес)wt(sj) <= t, где t -- максимальное число ошибок, исправляемых кодом. Таким образом полином ошибки есть e(x) = xn-jsj(x)(mod (1+xn))

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

x + x2 + x4 + x6 + x7 + x8 + x10 + x13

Найдем многочлен-синдром, (напомню, что g(x) = 1 + x4 + x6 + x7 + x8).

x + x2 + x4 + x6 + x7 + x8 + x10 + x13 (mod 1 + x4 + x6 + x7 + x8) = x2 + x6 + x8

Для кодового слова синдром, как известно, равен 0. В данном случае это не так, посланное слово было искажено помехой. В соответствии с описанной процедурой декодирования будем вычислять si(x) = xi(x2 + x6 + x8)(mod g(x)) для последовательных возрастающих значений i пока не найдем многочлен степени меньшей или равной двум (число ошибок t = 2 ).

s1 = xs(x)(mod g(x)) = (x3 + x7 + x9)(mod g(x)) = x3 + x4 + x5 + x6 + x7

s2 = x2s(x)(mod g(x)) = (x4 + x8 + x10)(mod g(x)) = 1 + x + x2 + x5

s3 = x3s(x)(mod g(x)) = (x5 + x9 + x11)(mod g(x)) = x + x2 + x3 + x6

s4 = x4s(x)(mod g(x)) = (x6 + x10 + x12)(mod g(x)) = x2 + x3 + x4 + x7

s5 = x5s(x)(mod g(x)) = (x7 + x11 + x13)(mod g(x)) = 1 + x3 + x5 + x6 + x7

s6 = x6s(x)(mod g(x)) = (x8 + x12 + x14)(mod g(x)) = x + 1

x + 1 имеет вес 2, поэтому для нахождения многочлена ошибок вычисляем e(x) = x15-6s6(x)(mod (1 + xn)) = x9(x + 1)(mod (1 + xn)) = x10 + x9.

Итак, если отправленное кодовое слово имеет не более двух ошибок, то оно было таким

(x + x2 + x4 + x6 + x7 + x8 + x10 + x13) + (x10 + x9) = x + x2 + x4 + x6 + x7 + x8 + x9 + x13

Этот многочлен соответствует вектору [011010111100010]. Чтобы восстановить само сообщение нам надо разделить кодовое слово на ПМ g(x) и получить

x + x2 + x4 + x5,

значит, сообщение было [0110110].

Программа №2 написана на Visual Basic. Данная программа по циклическому коду определяет порождающий и проверочный многочлены.

1. Производит разложение многочлена вида xn-1 на неприводимые многочлены в поле Fq.

2. Определяется максимальный (порождающий) многочлен.

3. Через порождающий многочлен определяется проверочный многочлен.

Листинг программы в приложении №2.

Методы построения циклических кодов.

В качестве информационных символов k для построения циклических кодов берут комбинацию двоичного кода на все сочетания. В общем случае, если заданную кодовую комбинацию G(X) умножить на образующий многочлен P(X), получится циклический код, обладающий теми или иными корректирующими свойствами в зависимости от выбора P(X). Однако в этом коде контрольные символы m будут располагаться в самых разнообразных местах кодовой комбинации. Такой код не является систематическим, что затрудняет его схемную реализацию. Ситуацию можно значительно упростить, если контрольные символы приписать в конце кода, т. е. после информационных символов.

Для этой цели удобно воспользоваться следующим методом.

Умножаем кодовую комбинацию G(X), которую мы хотим закодировать, на одночлен Xm , имеющий ту же степень, что и образующий многочлен P(X).

Делим произведение G(X)Xm на образующий многочлен P(X).

G(X)Xm / P(x)=Q(X)+R(X)/P(X),(1.1)

где Q(X) - частное от деления; R(X) - остаток.

Умножая выражение (1) на P(X) и перенося R(X) в другую часть равенства, согласно правилам алгебры двоичного поля, т. е. без перемены знака на обратный, получаем

F(X)=G(X)P(x)= G(X)Xm+R(X). (1.2)

Таким образом, согласно (2) , циклический код, т.е. закодированное сообщение F(X), можно образовать двумя способами:

умножением одной из комбинаций двоичного кода на все сочетания [комбинация Q)(X) к той же группе того же кода, что и заданная комбинация G(X)] на образующий многочлен P(X).

умножением заданной кодовой комбинации G(X) на одночлен Xm, имеющий ту же степень, что и образующий многочлен P(X), с добавлением к этому произведению остатка R(X), полученного после деления произведения G(X)Xm на образующий многочлен P(X).

Свойства образующего многочлена:

Все разрешенные комбинации циклического кода делятся на образующий многочлен без остатка.

На образующий многочлен делится без остатка двучлен Xn+1.

Задание 3. Постановка задачи. Код Файра. Построение кода Файра. Спецификация на программные модули

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

Тип кода: Файра

Число передаваемых сообщений: 63

Кодирующая способность кода: bs=3 br=4

Код Файра.

Под пакетом ошибок длинной b понимают такой вид комбинации помехи, в котором между крайними разрядами, пораженными помехами, содержится b-2 разряда.

Коды Файра могут исправлять пакет ошибок длинной bs и обнаруживать пакет ошибок длинной br (в кодах Файра понятие кодового расстояния d не используются).

Образующий многочлен кода Файра P(X)ф определяется из выражения

P(X)ф= P(X)(Xc-1),

Где P(X) - неприводимый многочлен степени L.

Из принципа построения кода следует, что

L ? bs, (1.3)

с ? bs+ br-1(1.4)

При этом с не должно делится нацело на число e, где

e=2L -1 (1.5)

Неприводимый многочлен P(X) выбирают из таблицы, согласно уравнению (3), но так, чтобы удовлетворялось условие (5). Длинна слова n равна наименьшему общему кратному чисел c и e, так как только в этом случае многочлен Xn+1 делится на P(X)ф без остатка:

n=НОК(e,c) (1.6)

Число контрольных символов

m=c+L (1.7)

В данной главе были рассмотрены теоретические аспекты построения двоичных циклических кодов. Также было выбрано кодирующее устройство на основе n-k разрядного регистра. Выяснили, что сначала необходимо найти образующий многочлен (по соответствующим формулам), а потом на основе этого многочлена строить кодирующее устройство. В последующих главах будет приведена реализация кодирующее устройство кода Файра на ЭВМ и приведена принципиальная схема кодера.

Построение кода Файра.

Согласно техническому заданию и в соответствии с данными, полученными на курсовую работу образующий многочлен Файра P(X)ф. Согласно формуле (1.3) находим L?3 , откуда можно принять L=3. Из соответствующих таблиц выбираем неприводимый многочлен P(X)=x3+x+1= 1011.

В соответствии с формулой (1.4):

c ? 3+4-1 ? 6 , откуда можно принять с=6.

По формуле (1.6) получаем е=23-1=7. Видим, что с на е нацело не делится.

Число проверочных разрядов, подставляя в формулу (1.7) значения L и C, получим m=6+3=9 .

Тогда длинна кода в соответствии с (1.6) равна

n = НОК(6,7) = 42

Тогда код Файра имеет вид (42,33).

Образующий многочлен Файра P(X)ф равен

P(X)ф=(x3+x+1)(x6+1)=x9+x7+x6+x3+x+1=1011001011(2.1)

Анализ технического задания.

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

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

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

Можно выделить пять основных модуля:

Основная программа.

В нём происходит обработка результатов выполнения остальных модулей программы. А именно: интерфейс, модуль ввода данных, модуль вывода данных, модуль обработки ошибок. Происходит выполнение алгоритма.

Модуль ввода.

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

Модуль вывода.

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

Модуль обработки ошибок.

В нём обрабатываются ошибки при вводе и реализована защита программы от сбоев.

Интерфейс.

В этом блоке реализован интерфейс программы взаимодействия пользователя с ЭВМ.

Интерфейс состоит из горизонтального меню и строки статуса.

Основные пункты меню:

О программе.

В этом пункте представлена краткая информация о программе.

Задание.

Изложена полная постановка задачи.

Работа.

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

Спецификация на программные модули.

Процедура initgrf.

Входные параметры:Нет.

Выходные параметры:Нет.

Выполняемые функции:Инициализация графики.

Особенностей:Нет.

Функция Sum(F,P: Byte): Byte;

Входные параметры: F,P: Byte

Выходные параметры: Sum

Выполняемые функции: Суммирование по модулю 2

Особенностей:Нет.

Процедура Dopoln(Var F: Mass1);

Входные параметры: F: Mass1

Выходные параметры: F: Mass1

Выполняемые функции: Умножение на старшую степень

образующего многочлена.

Особенности: НЕТ.

Процедура Delenye(F: Mass1; P: Mass2);

Входные параметры: F: Mass1;P: Mass2

Выходные параметры: нет.

Выполняемые функции: Деление многочлен на многочлен

Особенности: Имеет свои особенности.

Процедура Ed_Matrix(Var A: Two_Matrix);

Входные парамеры: Var A: Two_Matrix

Выходные параметры: Var A: Two_Matrix

Выполняемые функции: Составление единичной матрицы.

Особенности: нет.

Процедура Obr_Matrix(Var A: Two_Matrix);

Входные параметры A: Two_Matrix

Выходные параметры: A: Two_Matrix

Выполняемые функции: Получение образующей матрицы

Особенностей: нет.

Процедура Visual(Var sa:mass);

Входные параметры: Var sa:mass

Выходные параметры: Var sa:mass

Выполняемые функции: Ввод информационных символов.

Особенностей: нет

Процедура OutPutObr_Matrix(x,y : Integer;Obr_Matr :

Two_Matrix );

Входные параметры: x,y: Integer; Obr_Matr: Two_Matrix );

Выходные параметры:Нет.

Выполняемые функции: Вывод образующей матрицы.

Особенностей:Является универсальной.

Процедура OutPut(x,y : Integer;F,A : Mass1);

Входные параметры: x,y : Integer;F,A : Mass1.

Выходные параметры:Нет.

Выполняемые функции: Вывод полученной кодовой

комбинации.

Особенностей: нет.

Функция _Exit(Fon,Color : Integer;Col_Simv : Byte) :

integer;

Входные параметры Fon,Color : Integer;Col_Simv : Byte

Выходные параметры: _Exit : integer.

Выполняемые функции: выход из программы

Особенностей: нет

Основная программа

Входные параметры:нет.

Выходные параметры:Нет.

Выполняемые функции:Обьединяет в себя все процедуры и управляет работой.

Особенностей:Нет.

Результаты тестирования

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

Тестирование системы включало в себя:

- тестирование ввода различных набора данных;

- получение комбинаций для кода с любым образующим многочленом;

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

Список литературы

1. Лидл Р., Пильц Г. Прикладная абстрактная алгебра:

Учебное пособие / Перевод с англ. - Екатеринбург :

Изд-во Урал. ун-та, 1996г. - 744с.

2. http://yourtutor.narod.ru/cyclic/CyclicCodes.htm

Текст программных модулей

Uses Crt,Graph,AlexUnit;

Const

_N = 33;

_M = 10;

Type

Delim_Mas = array[1 .. 100] of byte;

Mass1 = array[1 .. _N+_M-1] of byte;

Mass2 = array[1 .. _M] of byte;

Mass3 = array[1 .. _M-1] of byte;

Mas_Exit=array[1..2] of String;

Two_Matrix=array[1 .. _N,1 .. _N+_M-1] of byte;

Const

P : Mass2 = (1,0,1,1,0,0,1,0,1,1);

Y_No : Mas_Exit = ('Да','Нет');

Var

F,Cicle_Kod : Mass1; R : Mass1;

Delimoe : Delim_Mas;

Obraz_Matrix : Two_Matrix;

Mas : Mass;

grDriver,grMode,ErrCode: Integer;

flag : boolean;

_t,c,n,m,i,schot,N0,Code : integer;

Function Sum(F,P : Byte) : Byte; {Суммирование по модулю 2}

Var

i : Byte;

Begin

If ((F=1) and (P=1)) or ((F=0) and (P=0)) Then Sum:=0

Else Sum:=1;

End;

{-------------------------------}

Procedure Dopoln(Var F : Mass1); {Умножение на старшую степень образующего многочлена}

Var

i : Byte;

Begin

for i:=_N+1 to _N+_M-1 do F[i]:=0;

End;

{--------------------------------}

Procedure Delenye(F : Mass1;P : Mass2); {Деление многочлен на многочлен}

Var

i,j,t : Byte; K : Mass1;

Begin

For i:=1 to _N do

Begin

IF F[i]=1 Then Begin

t:=1;

For j:=i to i+_M-1 do

Begin

K[j]:=Sum(F[j],P[t]);

F[j]:=K[j];

t:=t+1;

End;

End;

End;

t:=1;

For i:=_N+1 to _N+_M-1 do

Begin

R[t]:=F[i];

t:=t+1;

End;

End;

{----------------------------------------}

Procedure Ed_Matrix(Var A : Two_Matrix); {Составление единичной матрицы}

Var

i : Integer;

Begin

For i:=1 to _N do

Begin

A[i,_N+1-i]:=1

End;

End;

{----------------------------------------}

Procedure Obr_Matrix(Var A : Two_Matrix); {Получение образующей матрицы}

Var

i,j,t,Schot,l,m : Byte; K : Mass1;

Begin

Delimoe[1]:=1;

Schot:=1;

For i:=1 to _N do

Begin

IF Delimoe[i]=1 Then Begin

t:=1;

For j:=i to i+_M-1 do

Begin

K[j]:=Sum(Delimoe[j],P[t]);

Delimoe[j]:=K[j];

t:=t+1;

End;

l:=1;

For m:=i+1 to i+_M-1 do

Begin

A[Schot,_N+l]:=Delimoe[m];

l:=l+1;

End;

End

Else Begin

l:=1;

For m:=i+1 to i+_M-1 do

Begin

A[Schot,_N+l]:=Delimoe[m];

l:=l+1;

End;

End;

Schot:=Schot+1;

End;

End;

Procedure InitGrf; {Инициализация графики}

Begin

grDriver := Detect;

InitGraph(grDriver, grMode,'c:\sub\bp\bgi');

if GraphResult <> grOk then Begin

Halt(1);

End;

End;

Procedure Visual(Var sa:mass); {Ввод информационных символов}

Var i,x,y,k,Fon,Color,a:Integer;

Code: Integer;

ch,chi:Char;

Stop:Boolean;

Elm : String;

Begin

moveto(20,465);

SetTextJustify(0,1);

SetColor(0);

outtext('Нажмите Enter');

x:=30;

y:=225;

k:=17;

Fon:=1;

Color:=14;

Window_(30,150,610,260,1,'Ввод информационных символов');

SetTextStyle(1,0,4);

SetColor(Fon);

For i:=1 to _N Do

Begin

MoveTo(x+i*k,y);

Str(Sa[i],Elm);

OutText(Elm);

End;

SetTextStyle(0,0,1);

MoveTo(x+17,y-20);

Str(_N,Elm);

OutText(Elm);

MoveTo(x+_N*17,y-20);

Str(0,Elm);

OutText(Elm);

SetTextStyle(1,0,4);

i:=1;

MoveTo(x+i*k,y);

Setcolor(Color);

Str(Sa[i],Elm);

OutText(Elm);

Stop:=False;

Repeat

Begin

ch:=ReadKey;

Case ch Of

#75:Begin

Setcolor(Fon);

MoveTo(x+i*k,y);

Str(Sa[i],Elm);

OutText(Elm);

i:=i-1;

if(i<1)then i:=_N;

SetColor(Color);

MoveTo(x+i*k,y);

Str(Sa[i],Elm);

OutText(Elm);

Stop:=False;

End;{влево}

#77:Begin

SetColor(Fon);

MoveTo(x+i*k,y);

Str(Sa[i],Elm);

OutText(Elm);

i:=i+1;

if(i>_N)then i:=1;

SetColor(Color);

MoveTo(x+i*k,y);

Str(Sa[i],Elm);

OutText(Elm);

Stop:=False;

End;{вправо}

'1':Begin

SetColor(7);

MoveTo(x+i*k,y);

Str(Sa[i],Elm);

OutText(Elm);

SetColor(Color);

MoveTo(x+i*k,y);

sa[i]:=1;

F[i]:=Sa[i];

Str(Sa[i],Elm);

OutText(Elm);

Stop:=False;

End;

'2':Begin

SetColor(7);

MoveTo(x+i*k,y);

Str(Sa[i],Elm);

OutText(Elm);

SetColor(Color);

MoveTo(x+i*k,y);

sa[i]:=0;

F[i]:=Sa[i];

Str(Sa[i],Elm);

OutText(Elm);

Stop:=False;

End;

#13:Begin Stop:=True; End;

End;

End;

Until(Stop);

SetTextStyle(0,0,1);

End;

{---------------------------------------}

{Вывод образующей матрицы}

Procedure OutPutObr_Matrix(x,y : Integer;Obr_Matr : Two_Matrix );

Var k,i,j : Integer;

Elm : String;

Begin

k:=12;

For i:=1 to _N Do

Begin

For j:=1 to _N Do

Begin

MoveTo(x+j*k,i*10+y);

Str(Obr_Matr[i,j],Elm);

OutText(Elm);

End;

End;

SetColor(4);

For i:=1 to _N Do

Begin

For j:=_N+1 to _N+_M-1 Do

Begin

MoveTo(x+j*k,i*10+y);

Str(Obr_Matr[i,j],Elm);

OutText(Elm);

End;

End;

End;

{----------------------------------}

{Вывод полученной кодовой комбинации}

Procedure OutPut(x,y : Integer;F,A : Mass1);

Var k,s : Integer;

Elm : String;

Begin

MoveTo(x+10,y-20);

Str(_N+_M-1,Elm);

OutText(Elm);

MoveTo(x+(_N+_M)*12-3,y-20);

Str(0,Elm);

OutText(Elm);

k:=12;

For i:=1 to _N Do Cicle_Kod[i]:=F[i];

s:=1;

For i:=_N+1 To _N+_M-1 Do

Begin

Cicle_Kod[i]:=A[s];

s:=s+1;

End;

For i:=1 to _N Do

Begin

MoveTo(x+i*k,y);

Str(Cicle_Kod[i],Elm);

OutText(Elm);

End;

SetColor(4);

For i:=_N+1 to _N+_M-1 Do

Begin

MoveTo(10+x+i*k,y);

Str(Cicle_Kod[i],Elm);

OutText(Elm);

End;

End;

{---------------------------------}

{выход из программы}

Function _Exit(Fon,Color : Integer;Col_Simv : Byte) : integer;

Var x,y,k : Integer;

Stop : Boolean;

Ch : Char;

Begin

Window_(250,200,450,300,1,'Выход');

x:=225;

y:=260;

k:=80;

SetTextStyle(0,0,1);

SetColor(Col_Simv);

For i:=1 to 2 do

Begin

MoveTo(x+i*k,y);

OutText(Y_No[i]);

End;

i:=1;

SetFillStyle(1,Fon);

Bar(x+i*k-30,y-15,x+i*k+30,y+15);

MoveTo(x+i*k,y);

Setcolor(Color);

OutText(Y_No[i]);

Stop:=False;

Repeat

ch:=ReadKey;

Case ch Of

#75:Begin

SetFillStyle(1,7);

Bar(x+i*k-30,y-15,x+i*k+30,y+15);

Setcolor(Col_Simv);

MoveTo(x+i*k,y);

OutText(Y_No[i]);

i:=i-1;

if(i<1)then i:=1;

SetFillStyle(1,Fon);

Bar(x+i*k-30,y-15,x+i*k+30,y+15);

SetColor(Color);

MoveTo(x+i*k,y);

OutText(Y_No[i]);

Stop:=False;

End;{влево}

#77:Begin

SetFillStyle(1,7);

Bar(x+i*k-30,y-15,x+i*k+30,y+15);

Setcolor(Col_Simv);

MoveTo(x+i*k,y);

OutText(Y_No[i]);

i:=i+1;

if(i>2)then i:=2;

SetFillStyle(1,Fon);

Bar(x+i*k-30,y-15,x+i*k+30,y+15);

SetColor(Color);

MoveTo(x+i*k,y);

OutText(Y_No[i]);

Stop:=False;

End;{вправо}

#13:Begin Stop:=True; _Exit:=i End;

End;{Case}

Until Stop;

SetTextStyle(0,0,0);

End;

{---------------------------------}

{ОСНОВНАЯ ПРОГРАММА }

{---------------------------------}

Begin

InitGrf;

Repeat

flag:=false;

Fon(3,2,GetMaxX-3,30);

setcolor(0);

moveto(20,465);

SetTextJustify(0,1);

outtext('Esc - Выход');

Menu(3,'Работа','О программе','Помощь','','','');

Case t Of

1:Begin

Repeat

SetFillStyle(1,7); {Строка состояния}

Bar(3,450,getmaxx-3,getmaxy-3);

SetColor(15);

Line(3,450,getmaxx-3,450);

Line(3,450,3,getmaxy-3);

SetColor(0);

Line(3,getmaxy-3,getmaxx-3,getmaxy-3);

Line(getmaxx-3,450,getmaxx-3,getmaxy-3);

{moveto(20,465);

SetTextJustify(0,1);

SetColor(0);

outtext('Нажмите любую клавишу ...');}

VerMenu(3,'Ввод комбинации','Образующая матрица','Выход','','','');

Case Np Of

1 : Begin

Visual(Mas);

Dopoln(F);

Delenye(F,P);

Window_(30,300,610,410,1,'Закодированное сообщение. Красные

символы - контрольные.');

OutPut(40,370,F,R);

ReadKey;

SetFillStyle(1,3);

Bar(30,150,610,410);

End;

2 : Begin

Window_(30,50,610,445,1,'Образующая матрица');

Ed_Matrix(Obraz_Matrix);

Obr_Matrix(Obraz_Matrix);

OutPutObr_Matrix(40,90,Obraz_Matrix);

ReadKey;

SetFillStyle(1,3);

Bar(30,50,610,450);

End;

3 : Begin

Case _Exit(1,15,0) of

1 : begin

Np:=3;

flag:=true;

end;

2 : Flag:=False;

end

End;

End;

Until (Np=3) or (Np=4);

Ramka_Off(x1,y1,x2,y2);

End;

2:Begin

SetFillStyle(1,7); {Строка состтояния}

Bar(3,450,getmaxx-3,getmaxy-3);

SetColor(15);

Line(3,450,getmaxx-3,450);

Line(3,450,3,getmaxy-3);

SetColor(0);

Line(3,getmaxy-3,getmaxx-3,getmaxy-3);

Line(getmaxx-3,450,getmaxx-3,getmaxy-3);

Window_(100,80,510,400,1,'О программе');

moveto(130,130);

SetTextJustify(0,1);

outtext('Данная программа является дипломной работой');

moveto(300,145);

SetTextJustify(1,1);

outtext('для направления математика');

moveto(300,160);

SetTextJustify(1,1);

outtext('специальность математика. Степень акалавра.');

moveto(120,200);

SetTextJustify(0,1);

outtext('Задание: Построить программу кодирования/декодирования');

moveto(185,220);

outtext('для кода Файра. Кодируемых сообщений 63,');

moveto(185,240);

outtext('число обнаруживаемых ошибок Br=4, число');

moveto(185,260);

outtext('исправляемых ошибок Bs=3.');

moveto(120,290);

outtext('Студент : Нургалеев А.Р.');

moveto(120,310);

outtext('Группа : ММ-401');

moveto(120,330);

outtext('Преподаватель : Зюляркина Н.Д.');

moveto(300,380);

SetTextJustify(1,1);

outtext('Челябинск 2005 г.');

moveto(20,465);

SetTextJustify(0,1);

SetColor(0);

outtext('Нажмите любую клавишу ...');

Readkey;

Ramka_Off(x1,y1,x2,y2);

End;

3:Begin

SetFillStyle(1,7); {Строка состтояния}

Bar(3,450,getmaxx-3,getmaxy-3);

SetColor(15);

Line(3,450,getmaxx-3,450);

Line(3,450,3,getmaxy-3);

SetColor(0);

Line(3,getmaxy-3,getmaxx-3,getmaxy-3);

Line(getmaxx-3,450,getmaxx-3,getmaxy-3);

Window_(100,50,500,350,1,'Помощ');

moveto(120,110);

SetTextJustify(0,1);

outtext('<-- --> ПЕРЕДВИЖЕНИЕ ПО ГОРИЗОНТАЛЬНОМУ МЕНЮ.');

moveto(120,130);

outtext('_ |');

moveto(120,135);

outtext('| | ПЕРЕДВИЖЕНИЕ ПО ВЕРТИКАЛЬНОМУ МЕНЮ.');

moveto(120,140);

outtext('| ');

moveto(114,150);

moveto(114,155);

outtext('<Enter> АКТИВАЦИЯ ПУНКТА МЕНЮ.');

moveto(140,200);

outtext('В программе использованы соотношения :');

moveto(120,220);

outtext('L >= Bs c >= Bs+Br-1');

moveto(160,235);

outtext('L');

moveto(120,240);

outtext('e = 2 -1 m = c + L');

moveto(120,260);

outtext('n = НОК(e,c)');

moveto(120,280);

outtext('После расчетов получили образующий многочлен');

moveto(120,300);

outtext('Файра : P(x)=1011001011');

moveto(20,465);

SetTextJustify(0,1);

SetColor(0);

outtext('Нажмите любую клавишу ...');

ReadKey;

Ramka_Off(x1,y1,x2,y2);

End;

End; {Case}

Until flag;

closegraph;

End.

Размещено на Allbest.ru