3

Введение

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

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

История помехоустойчивого кодирования началась в 1948г. публикацией знаменитой статьи Клода Шеннона. Шеннон показал, что с каждым каналом связано измеряемое в битах в секунду и называемое пропускной способностью канала число С, имеющее следующее значение. Если требуемая от системы связи скорость передачи информации R (измеряемая в битах в секунду) меньше С, то, используя помехоустойчивые коды, для данного канала можно построить такую систему связи, что вероятность ошибки на выходе будет сколь угодно мала [1]. Из теории Шеннона следует, что построение слишком хороших каналов связи является расточительством, экономически выгодней использовать помехоустойчивое кодирование. Шеннон, однако, не показал, как найти подходящие коды, а лишь доказал их существование. В пятидесятые годы много усилий было потрачено на попытки построения в явном виде классов кодов, позволяющих получить обещанную сколь угодно малую вероятность ошибки, но результаты были скудными. В следующем десятилетии решению этой увлекательной задачи уделялось меньше внимания, вместо этого исследователи кодов предприняли длительную атаку по двум направлениям.

Первое направление носило чисто алгебраический характер и преимущественно рассматривало блоковые коды. Первые блоковые коды были введены в 1950г., когда Хэмминг описал класс блоковых кодов, исправляющих одиночные ошибки. Коды Хэмминга были разочаровывающе слабы по сравнению с обещанными Шенноном гораздо более сильными кодами. Несмотря на усиленные исследования, до конца пятидесятых годов не было построено лучшего класса кодов. В течение этого периода без какой-либо общей теории были найдены многие коды с малой длиной блока. Основной сдвиг произошел, когда Боуз и Рой-Чоудхури и Хоквингем[1] нашли большой класс кодов, исправляющих кратные ошибки (коды БЧХ), а Рид и Соломон [1960] нашли связанный с кодами БЧХ класс кодов для недвоичных каналов. Хотя эти коды остаются среди наиболее важных классов кодов, общая теория помехоустойчивых блочных кодов с тех пор успешно развивалась, и время от времени удавалось открывать новые коды.

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

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

В данном курсовом проекте необходимо разработать декодер кода Рида - Маллера с параметрами (n, k) = (32, 26).

Коды Рида - Маллера (РМ коды) являются одним из наиболее старых и хорошо изученных семейств кодов. Минимальное расстояние РМ кодов меньше, чем минимальное расстояние кодов БЧХ, за исключением кодов первого порядка и кодов с умеренными длинами. Однако большим достоинством РМ кодов является то, что они достаточно просто декодируются при помощи мажоритарно-логических устройств. Интересной особенностью кодов Рида - Маллера является то, что код Рида - Маллера r-го порядка дуален коду Рида - Маллера (m - r - 1)-го порядка

РМ коды являются простейшим примером класса геометрических кодов. Этот класс содержит также евклидово-геометрические и проективно- геометрические коды. Все коды этого класса допускают мажоритарное декодирование.

Коды Рида - Маллера характеризуются следующими параметрами[2]:

r - порядок кода, m - некоторое число, большее r, причем:

n = 2^m (1),

d₀ = 2^m-r (2),

(3),

где - число сочетаний i по m.

Код Рида - Маллера может исправлять следующее число ошибок[2]:

(4).

1. Основные сведения о коде

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

Блоковый код мощности М над алфавитом из q символов определяется как множество из М q-ичных последовательностей длины n, называемых кодовыми словами (если q = 2, то символы называются битами).

При этом М = q^k для некоторого целого k , код называется (n, k)-кодом. Причем каждой последовательности из k q-ичных символов можно сопоставить последовательность из n q-ичных символов, являющуюся кодовым словом. Имеются два основных класса кодов: блоковые коды и древовидные коды (смотри рисунок 1).

2

В теории блоковых кодов доказывается тот факт, что хорошими являются коды с большой длиной кода и очень хорошими являются коды с очень большой длиной блока.

О блоковом коде судят по трем параметрам: длине блока n, информационной длине k и минимальному кодовому расстоянию d.

Расстоянием по Хэммингу [1] между двумя q-ичными последовательностями x и y длины n называется число позиций, в которых они различны. Это расстояние обозначается через d (x, y).

Минимальным кодовым расстоянием кода [1] называется наименьшее из всех расстояний по Хэммингу между различными парами кодовых слов, т.е.

(5),

(n, k)-код с минимальным расстоянием d называется также (n, k, d)-кодом.

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

(6).

Геометрическая иллюстрация дается на рисунке 2. В пространстве всех q-ичных n-последовательностей выбрано некоторое множество n-последовательностей, объявленных кодовыми словами. Если d' - минимальное расстояние этого кода, а t - наибольшее целое число, удовлетворяющее условию , то вокруг каждого кодового слова можно описать непересекающуюся сферу радиуса t. Принятые слова, лежащие внутри сфер, декодируются как кодовое слово, являющееся центром

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

Некоторые принятые слова, содержащие более t ошибок, попадут внутрь сферы, описанной вокруг другого кодового слова, и будут декодированы неправильно. Другие принятые слова, содержащие более t ошибок, попадут в промежуточные между сферами декодирования области.

Полем [3] называется множество с двумя определенными на нем операциями - сложением и умножением, причем имеют место следующие аксиомы:

1) множество образует абелеву группу по сложению;

2) поле замкнуто относительно умножения, и множество ненулевых элементов образуют абелеву группу по умножению.

3) закон дистрибутивности:

(a + b)c = ac+bc для любых a, b, c из поля.

Поле с q элементами, если оно существует, называется конечным полем, или полем Галуа [2], и обозначается через GF(q).

Линейный код образует подпространство в GF(q). Любое множество базисных векторов может быть использовано в качестве строк для построения (kn)-матрицы G, которая называется порождающей матрицей кода. Пространство строк матрицы G есть линейный код, любое кодовое слово есть линейная комбинация строк из G. Множество q^k кодовых слов называется линейным (n, k)-кодом.

Строки матрицы G линейно независимы, и число строк k равно размерности подпространства. Размерность всего пространства GFⁿ(q) может быть отображена на множество кодовых слов.

Любое взаимно однозначное соответствие k-последовательностей и кодовых слов может быть использовано для кодирования, но наиболее естественный способ кодирования использует отображение

c = iG (7),

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

Например, если

,

то информационное слово

i = [0 1 1]

будет кодироваться в кодовое слово

Кроме порождающей матрицы существует так же проверочная матрица называемая Н матрицей. При этом выполняется условие

сН^Т=0 (8).

Матрица Н является (n - k)n матрицей; поскольку равенство сН^Т = 0 выполняется при подстановке вместо с любой строки матрицы G, то

GH^T = 0 (9).

Для приведенной выше порождающей матрице G, получаем

.

Коды Рида - Маллера представляют собой класс линейных кодов над GF(2) c простым описанием и декодированием, осуществляемым методом простого голосования. По этим причинам коды Рида - Маллера играют важную роль в кодировании (коды Рида - Маллера были использованы при передаче фотографий Марса космическим кораблем Маринер в 1972г.)[2], хотя если судить по минимальному расстоянию, то, за некоторыми исключениями, они не заслуживают особого внимания. Для любых целых m и r < m существует код Рида - Маллера r-го порядка длины 2m.

Код Рида - Маллера является линейным кодом и определяется через порождающую матрицу, которая обычно, для удобства декодирования, строится в несистематической форме. Покомпонентным произведением двух векторов a = (a₀, a₁, … a_n-1) и b = (b₀, b₁, … b_n-1) является вектор

с = (a₀b₀, a₁b₁, … a_n-1b_n-1) (10).

Порождающая матрица кода Рида - Маллера r-го порядка длиной 2^m определяется как совокупность блоков

,

где G₀ - вектор размерности n = 2^m, состоящий из одних единиц; G₁ есть (m2^m)-матрица, содержащая в качестве столбцов все двоичные m-последовательности; строки матрицы G_l получаются из строк матрицы G₁ как всевозможные произведения l строк из G₁. Считается, что первый столбец в G₁ состоит из одних нулей, последний - из одних единиц, а остальные m последовательности в G₁ расположены в порядке возрастания, считая, что младший бит расположен в нижней строке. Существует всего способов выбора l строк, входящих в произведение, следовательно матрица G_l имеет размер . Отсюда следует, что для кода Рида - Маллера порядка r

Что обеспечивается линейной независимостью строк в матрице G. Код нулевого порядка является (n, 1)-кодом. Это просто код с повторением, который тривиально декодируется с помощью мажоритарного метода. Минимальное расстояние такого кода равно 2^m.

Например, возьмем m = 4, n = 16, r = 3. Тогда

,

.

Поскольку G₁ имеет 4 строки, матрица G₂ имеет строк:

,

а матрица G₃ имеет строк:

Таким образом, порождающая матрица кода Рида - Маллера третьего порядка длины 16 является (1516)-матрицей вида

.

Эта порождающая матрица задает (16, 15)-код над GF(2) (на самом деле это просто код с проверкой на четность). Другой код Рида - Маллера может быть получен с использованием этих матриц, если взять r = 2. В этом случае порождающая матрица будет иметь вид

и задает (16, 11)-код над GF(2). В действительности это (15, 11)-код Хэмминга, расширенный с помощью проверки на четность.

Из определения порождающей матрицы ясно, что код Рида - Маллера r-го порядка может быть получен дополнением кода Рида - Маллера (r - 1)-го порядка, а код Рида - Маллера (r - 1)-го порядка получается из кода r-го порядка с помощью выбрасывания. Поскольку код Рида - Маллера r-го порядка содержит код (r - 1)-го порядка, ясно, что его минимальное расстояние не может быть больше минимального расстояния кода (r-1)-го порядка. Вообще, кодовое расстояние кода Рида - Маллера определяется по формуле

d = 2^{m - r} (13).

Каждая строка матрицы G₁ имеет вес 2^{m - l}. Таким образом, любая строка матрицы G имеет четный вес, а сумма двух двоичных векторов четного веса также имеет четный вес. Следовательно все линейные комбинации строк матрицы G имеют четный вес, а это значит, что все кодовые слова имеют четный вес. Матрица G_r содержит строки весом 2^{m - r}, и, следовательно, минимальный вес кода не превосходит 2^{m - r}.

Для декодирования кодов Рида - Маллера был специально разработан алгоритм Рида [2], который позволяет исправлять ошибок и восстанавливать k информационных символов. Отсюда следует, что минимальное расстояние будет не меньше 2^{m - r} - 1, но оно должно быть четным и потому будет не меньше 2^{m - r}.

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

Для удобства разобьем информационный вектор на r + 1 сегмент, положив , где сегмент I_l содержит информационных битов. Каждый сегмент будет умножаться на один блок матрицы G. Следовательно, кодирование можно представить поблочным умножением вектора на матрицу:

(14).

Предположим, что информационная последовательность разбита на сегменты следующим образом: каждому сегменту соответствует один из r блоков порождающей матрицы, который при кодировании умножается на этот сегмент. Если мы сможем восстановить информационные биты в r-ом сегменте, то затем сможем вычислить их вклад в принятое слово и вычесть его из принятого слова. Тогда задача сведется к декодированию кода Рида - Маллера (r - 1)-го порядка. Процедура декодирования представляет собой последовательность мажоритарных декодирований и начинается с нахождения мажоритарным методом информационных символов в сегменте м номером r.

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

(15).

Алгоритм декодирования сначала по принятому слову восстанавливает I_r, затем вычисляется разность

(16),

которая является искаженным кодовым словом кода Рида - Маллера (r - 1)-го порядка.

Прежде всего, рассмотрим декодирование информационного бита i_k-1, который умножается на последнюю строку матрицы G_r. Декодируем этот бит, вычисляя 2^{m - r} проверочных сумм по 2^r бит из 2^m бит принятого слова, так что каждый принятый бит входит только в одну сумму. Проверочные суммы строятся таким образом, что символ i_k-1 вносит вклад только в один бит, а все другие информационные биты вносят вклад в четное число бит в каждой проверочной сумме. Таким образом, при отсутствии ошибок все проверочные суммы равны i_k-1. Но, даже если имеется не более ошибок, большинство проверочных сумм по-прежнему будет равняться i_k-1.

Первая проверочная сумма представляет собой сумму по модулю 2 первых 2 бит принятого слова, вторая - сумму по модулю два вторых 2^r бит принятого слова и т.д. Всего получается 2^{m - r} проверочных сумм, и по предположению имеется ошибок. Таким образом, мажоритарное голосование проверочных сумм дает правильное значение i_k-1. Для построенного ранее (16, 11)-кода Рида - Маллера эти четыре суммы выглядят следующим образом:

Если произошла только одна ошибка, то одна из оценок, даваемых проверочными суммами, будет неверна; мажоритарное решение дает значение i₁₀. Если произошло две ошибки, то ни одно значение проверочных сумм не встречается чаще других и обнаруживается одна ошибка.

Аналогично может быть продекодирован любой информационный символ, который умножается на одну из строк матрицы G_r. Это происходит потому, что любая строка матрицы G_r ничем не выделяется среди остальных. Перестановкой столбцов мы можем добиться того, что любая строка будет выглядеть так же, как последняя строка матрицы G_r. Следовательно, можно использовать те же самые проверочные суммы, соответственно переставив индексы у символов, входящих в эти суммы. После построения 2^{m - r} проверочных сумм каждый бит декодируется мажоритарным методом.

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

Этот процесс повторяется до тех пор, пока не будут найдены все информационные биты.

2. Выбор и обоснование параметров кода

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

Итак в данном курсовом проекте необходимо построить декодер кода Рида-Маллера, исправляющий одиночную ошибку и длиной информационного слова в тридцать два бита. Из формул и n = 2^m находим, что m = 5, а r = 3.

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

Из формулы d₀ = 2^m-r находим, что d₀ = 4.

Следовательно, в курсовом проекте необходимо построить декодер кода Рида - Маллера третьего порядка (РМ-3) с параметрами (n, k, d₀) = (32, 26, 4), исправляющий одиночную ошибку.

3. Разработка структурной электрической схемы декодера

В данной курсовой работе необходимо построить декодер кода Рида -Маллера с параметрами m = 5, n = 32, r = 3.

Построим проверочную G матрицу:

,

,

,

,

Запишем в полном виде:

Будем декодировать этот код алгоритмом Рида, который был описан ранее. Так как данный код является кодом Рида - Маллера 3-го порядка, то число уравнений для бит с 16-го по 25-й равно 2^m-r = 4, а число членов в каждом уравнении равно 2^r = 8.

Запишем уравнения для последнего 25-го бита:

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

Следуя этому принципу, строятся уравнения для бит с 16-го по 24-й. Приведем их.

Уравнения для 24-го бита:

Уравнения для 23-го бита:

Уравнения для 22-го бита:

Уравнения для 21-го бита:

Уравнения для 20-го бита:

Уравнения для 19-го бита:

Уравнения для 18-го бита:

Уравнения для 17-го бита:

Уравнения для 16-го бита:

Для того чтобы декодировать остальные биты, необходимо из них вычесть вклад тех информационных бит, которые уже были найдены, а затем произвести декодирование с помощью кода Рида - Маллера меньшего (на единицу) порядка. То есть необходимо найти v' = v - (a1a2a3i0 +…+ a3a4a5i31).

Запишем уравнения, с помощью которых происходит вычет уже известных символов из принятого слова, с учетом того, что операция вычитания в GF(2) эквивалентна операции суммы по модулю 2:

Проделав эти операции, будем декодировать символы v' с помощью порождающей матрицы 2-го порядка. Для этого необходимо отбросить нижние десять строк матрицы G. Следовательно, матрица G' будет иметь вид:

Теперь мы можем составить уравнения для бит, начиная с 6-го и кончая 15-м. Исходя из формул, число уравнений для декодирования каждого бита будет рано 2^m-r = 8, число слагаемых в каждом уравнении будет равно 2^r = 4. Эти уравнения составляются по тем же принципам, как и уравнения для декодирования предыдущих бит.

Приведем эти уравнения.

Уравнения для 15-го бита:

Уравнения для 14-го бита:

Уравнения для 13-го бита:

Уравнения для 12-го бита:

Уравнения для 11-го бита:

Уравнения для 10-го бита:

Уравнения для 9-го бита:

Уравнения для 8-го бита:

Уравнения для 7-го бита:

Уравнения для 6-го бита:

Чтобы найти биты с 1-го по 5-й, необходимо вычесть вклад тех информационных бит, которые были найдены ранее, а затем произвести декодирование с помощью кода Рида - Маллера меньшего порядка (1-го). То есть необходимо найти v'' = v' - (a₁a₂i₀ +…+ a₄a₅i₃₁).

Запишем уравнения, с помощью которых происходит вычет уже известных символов из принятого слова, с учетом того, что операция вычитания в GF(2) эквивалентна операции суммы по модулю 2:

Проделав эти операции, будем декодировать символы v'' с помощью порождающей матрицы 1-го порядка. Для этого необходимо отбросить нижние десять строк матрицы G'. Следовательно, матрица G'' будет иметь вид:

Теперь мы можем составить уравнения для бит, начиная с 1-го и кончая 5-м. Исходя из формул, число уравнений для декодирования каждого бита будет равно 2^m-r = 16, число слагаемых в каждом уравнении будет равно 2^r = 2. Эти уравнения составляются по тем же принципам, как и уравнения для декодирования предыдущих бит. Приведем эти уравнения.

Уравнения для 5-го бита:

Уравнения для 4-го бита:

Уравнения для 3-го бита:

Уравнения для 2-го бита:

Уравнения для 1-го бита:

Для декодирования 0-го бита необходимо вычесть вклад найденных ранее информационных бит из значения v''. То есть необходимо найти v''' = v'' - (a₁i₀ +…+ a₅i₃₁).

Запишем уравнения, с помощью которых происходит вычет уже известных символов из принятого слова, с учетом того, что операция вычитания в GF(2) эквивалентна операции суммы по модулю 2:

Декодирование нулевого бита происходит очень просто - по большинству среди всех бит v'''.

Теперь, зная все этапы декодирования по алгоритму Рида, для данного кода можно составить структурную схему декодера. Она представлена на рисунке 4.

4. Разработка функциональной электрической схемы декодера

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

Входной регистр.

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

Блок, находящий биты с 16-го по 25-й.

Этот блок находит последние 10 информационных бит. В нем используются сумматоры по модулю два и мажоритарные элементы на четыре входа. Так, для 25-го бита схема будет иметь вид, показанный на рисунке 5.



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

Блок, вычитающий из принятого слова найденные биты (с16-го по 25-й).

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

Блок, находящий биты с 6-го по 15-й.

Этот блок находит 10 информационных бит с 6-го по 15-й. В нем используются сумматоры по модулю два и мажоритарные элементы на восемь входов. Так, для 15-го бита схема будет иметь вид, показанный на рисунке 7.

Блок, вычитающий из принятого слова найденные биты (с 6-го по 15-й).

Как было сказано ранее, для того, чтобы декодировать остальные биты, необходимо вычесть из кодовых символов вклад тех информационных бит, которые уже найдены (с 6-го по 15-й). Уравнения для этой операции также были приведены ранее. Функциональная схема этого блока приведена на рисунке 8.

Блок, находящий биты с 1-го по 5-й.

Этот блок находит 10 информационных бит с 1-го по 5-й. В нем используются сумматоры по модулю два и мажоритарные элементы на шестнадцать входов. Так, для 5-го бита схема будет иметь вид, показанный на рисунке 9.

Блок, вычитающий из принятого слова найденные биты (с 1-го по 5-й).

Как было сказано ранее, для того, чтобы декодировать нулевой бит, необходимо вычесть из кодовых символов вклад тех информационных бит, которые уже найдены (с 1-го по 5-й). Уравнения для этой операции также были приведены ранее. Функциональная схема этого блока приведена на рисунке 10.

Блок, находящий нулевой бит.

Блок, находящий нулевой бит, представляет собой просто мажоритарный элемент на 32 входа. Он представлен на рисунке 11.

5. Разработка блок-схемы алгоритма

Алгоритм работы декодера кода Рида - Маллера будем разрабатывать на основе уже приведенных выше уравнений. Алгоритм приведен на рисунке 12.

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

Работа блок-схемы и, естественно, программы происходит по тем же принципам и уравнениям, что и работа структурной схемы декодера кода Рида - Маллера (смотри рисунок 4).

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

Исходный текст программы смотри в приложении 1. Скомпилированная программа находится в приложении 2 (дискета).

6. Выбор языка программирования, достоинства и недостатки

Для реализации данного декодера программным путем был выбран язык программирования С++. Язык программирования С++ был разработан Бьерном Страуструпом для компании AT&T[5]. С++ является обьектно-ориентированым расширением языка програмирования С, который, в свою очередь, был разработан Д. Ритчи[5].

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

Итак, достоинствами языка С являются самая высокая производительность программ, написанных на нем (исключая, конечно, ассемблер), высокая скорость разработки и так называемая “статическая кросс-платформенность”, то есть для переноса программ достаточно перекомпилировать эту программу на этой платформе (компиляторы С сейчас есть практически на всех платформах). По этой причине язык програмирования С часто называют “переносимым ассемблером”. Именно по этим причинам на языке С (и С++) написаны такие системы, как Windows (начиная с версии 3.0), UNIX, LINUX [5]. Для операционных систем UNIX и LINUX язык С вообще является “родным” языком, то есть в стандартный пакет этих систем всегда входит редактор исходных текстов и компилятор языка С.

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

Первый недостаток, то есть отсутствие обьектно-ориентированных элементов и конструкций в языке, привел к созданию нового обьектно-ориентированного языка С++. С++ фактически является надмножеством языка С. Именно по этой причине С++ часто называют не “чистым” объектно-ориентированным, а гибридным языком програмирования, что, конечно, является его достоинством.

С++ не первый объектно-ориентированный язык програмирования, как многие считают (он наоборот один из последних), но все объектно-ориентированные языки, которые были разработаны до него (да и после тоже, за редким исключением), обладают крайне низкой производительностью, а потому не могли применяться для реальной разработки программ. Язык С++ содержит в себе все элементы языка С, плюс к этому вносит три “кита” обьектно-ориентированного языка - инкапсуляцию, наследование и виртуальный механизм.

Итак, к достоинствам языка С++ относятся все достоинства языка С. Прежде всего это производительность. Он безусловно самый быстрый из всех обьектно-ориентированных языков програмирования (скорость программ, написанных на С++, практически такова, как и программ, написанных на “чистом” C). Во-вторых, объектно-ориентированные элементы языка позволяют строить эффективные и грамотные физические, математические и другие модели, работающие с максимальным быстродействием, в кратчайшие сроки. Кроме того, используя наследование, можно создавать объектно-ориентированные библиотеки, значительно сокращающие разработку. Тем более что сейчас с появлением технологии COM (Component Object Model) [5] эти библиотеки можно перенести на ее основу и они станут доступны для использования всеми программами не зависимо от того, на каких языках они были написаны.

К недостаткам языка можно отнести все тот же сложный и запутанный синтаксис, который после внесения в него новых элементов стал еще сложнее и запутанней. Часто к недостаткам языка относят то, что он является гибридным языком, а не “чисто” объектно-ориентированным. Но при этом забывается, что С++ содержит все, именно все элементы объектно-ориентированного языка, но также он содержит опять же все элементы структурного языка (ведь язык С является подмножеством языка С++). Поэтому разработчик может выбирать (или комбинировать), какие в данном случае элементы языка нужно использовать: объектно-ориентированные или структурные. Это придает языку особую гибкость.

Программа к данному курсовому проекту была написана на языке Microsoft Visual C++ 6.0.

Заключение

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

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

В этом курсовом проекте мы программно построили декодер кода Рида - Маллера с параметрами (n, k, d)=(32, 26, 4), декодируя его алгоритмом Рида, для чего построили структурную, функциональную схемы декодера кода Рида - Маллера алгоритмом Рида. Для того чтобы их построить, мы вначале получили уравнения для декодирования 10 бит с 16-го по 25-й. Затем мы вычли из полученного слова вклад, вносимый в них уже известными информационными символами, для чего получили соответствующие уравнения.

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

Затем мы декодировали биты, начиная, с 1-го по 5-й, так, как если бы это был код Рида - Маллера первого порядка, по опять же полученным нами уравнениям. И наконец, в последний раз мы вычитаем из кодовых символов найденные нами информационные символы, вносящие вклад в них.

Теперь мы находим 0-й бит информационной последовательности по простому большинству среди всех бит кодового слова.

Далее мы построили блок-схему алгоритма декодирования кода Рида - Маллера алгоритмом Рида в соответствии со структурной, функциональной схемами и теми уравнениями, которые получили для декодирования отдельных бит и для вычета их вклада из кодового слова. По этому алгоритму мы разработали программу декодирования кода Рида - Маллера с параметрами (n, k, d) = (32, 26, 4) на языке С++, краткую характеристику которого, его достоинства и недостатки представили в данном курсовом проекте.

Мы также узнали, что алгоритм Рида позволяет исправлять много ошибок, вес которых больше . Этот факт был доказан Дюком [2]. А общее число исправляемых ошибок подсчитал Кричевский.

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

Литература

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. Москва: Мир, 1986 г.

2. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979 г.

3. Дмитриев В. И. Пр-кладная теория информации. М.: Высшая школа, 1989г.

4. Дж. Кларк, Дж. Кейн. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радиосвязь, 1987 г.

5. Круглински Девид Дж., Основы Visual C++/Пер. с англ. - М.: Издательский отдел “Русская редакция”, 1997 г.

Приложение

Файл Rid.h

// Decoder Rid.h : main header file for the DECODER RID application

//

#if !defined(AFX_DECODERRID_H__C9444801_9582_4E12_9425_33567A600AF2__INCLUDED_)

#define AFX_DECODERRID_H__C9444801_9582_4E12_9425_33567A600AF2__INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

#ifndef __AFXWIN_H__

#error include 'stdafx.h' before including this file for PCH

#endif

#include "resource.h" // main symbols

/////////////////////////////////////////////////////////////////////////////

// CDecoderRidApp:

// See Decoder Rid.cpp for the implementation of this class

//

class CDecoderRidApp : public CWinApp

{

public:

CDecoderRidApp();

// Overrides

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL(CDecoderRidApp)

public:

virtual BOOL InitInstance();

//}}AFX_VIRTUAL

// Implementation

//{{AFX_MSG(CDecoderRidApp)

// NOTE - the ClassWizard will add and remove member functions here.

// DO NOT EDIT what you see in these blocks of generated code !

//}}AFX_MSG

DECLARE_MESSAGE_MAP()

};

/////////////////////////////////////////////////////////////////////////////

//{{AFX_INSERT_LOCATION}}

// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif // !defined(AFX_DECODERRID_H__C9444801_9582_4E12_9425_33567A600AF2__INCLUDED_)

Файл RidDlg.h

// Decoder RidDlg.h : header file

//

#if !defined(AFX_DECODERRIDDLG_H__99108337_398F_43EE_8F95_D7AB96593444__INCLUDED_)

#define AFX_DECODERRIDDLG_H__99108337_398F_43EE_8F95_D7AB96593444__INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

/////////////////////////////////////////////////////////////////////////////

// CDecoderRidDlg dialog

class CDecoderRidDlg : public CDialog

{

// Construction

public:

CDecoderRidDlg(CWnd* pParent = NULL); // standard constructor

// Dialog Data

//{{AFX_DATA(CDecoderRidDlg)

enum { IDD = IDD_DECODERRID_DIALOG };

CString m_codestring;

CString m_decodeword;

//}}AFX_DATA

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL(CDecoderRidDlg)

protected:

virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support

//}}AFX_VIRTUAL

// Implementation

protected:

HICON m_hIcon;

// Generated message map functions

//{{AFX_MSG(CDecoderRidDlg)

virtual BOOL OnInitDialog();

afx_msg void OnSysCommand(UINT nID, LPARAM lParam);

afx_msg void OnPaint();

afx_msg HCURSOR OnQueryDragIcon();

afx_msg void OnChangeCodeword();

afx_msg void OnDecoder();

//}}AFX_MSG

DECLARE_MESSAGE_MAP()

private:

int Majorit32(int sum);

void DecrementR1();

int Majorit16(int sum);

void DecrementR2();

int Majorit8(int sum);

int mod2(int* m, int number);

void DecrementR3();

int Majorit4(int sum);

void Init();

int decordword[26];

int codword[32];

};

//{{AFX_INSERT_LOCATION}}

// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif // !defined(AFX_DECODERRIDDLG_H__99108337_398F_43EE_8F95_D7AB96593444__INCLUDED_)

Файл Decoder Rid.cpp

// Decoder Rid.cpp : Defines the class behaviors for the application.

//

#include "stdafx.h"

#include "Decoder Rid.h"

#include "Decoder RidDlg.h"

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif

/////////////////////////////////////////////////////////////////////////////

// CDecoderRidApp

BEGIN_MESSAGE_MAP(CDecoderRidApp, CWinApp)

//{{AFX_MSG_MAP(CDecoderRidApp)

// NOTE - the ClassWizard will add and remove mapping macros here.

// DO NOT EDIT what you see in these blocks of generated code!

//}}AFX_MSG

ON_COMMAND(ID_HELP, CWinApp::OnHelp)

END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////

// CDecoderRidApp construction

CDecoderRidApp::CDecoderRidApp()

{

// TODO: add construction code here,

// Place all significant initialization in InitInstance

}

/////////////////////////////////////////////////////////////////////////////

// The one and only CDecoderRidApp object

CDecoderRidApp theApp;

/////////////////////////////////////////////////////////////////////////////

// CDecoderRidApp initialization

BOOL CDecoderRidApp::InitInstance()

{

AfxEnableControlContainer();

// Standard initialization

// If you are not using these features and wish to reduce the size

// of your final executable, you should remove from the following

// the specific initialization routines you do not need.

#ifdef _AFXDLL

Enable3dControls(); // Call this when using MFC in a shared DLL

#else

Enable3dControlsStatic(); // Call this when linking to MFC statically

#endif

CDecoderRidDlg dlg;

m_pMainWnd = &dlg;

int nResponse = dlg.DoModal();

if (nResponse == IDOK)

{

// TODO: Place code here to handle when the dialog is

// dismissed with OK

}

else if (nResponse == IDCANCEL)

{

// TODO: Place code here to handle when the dialog is

// dismissed with Cancel

}

// Since the dialog has been closed, return FALSE so that we exit the

// application, rather than start the application's message pump.

return FALSE;

}

/////////////////////////////////////////////////////////////////////////////

//{{AFX_INSERT_LOCATION}}

// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif // !defined(AFX_DECODERRID_H__C9444801_9582_4E12_9425_33567A600AF2__INCLUDED_)

Файл Decoder Rid.cpp

// Decoder RidDlg.cpp : implementation file

//

#include "stdafx.h"

#include "Decoder Rid.h"

#include "Decoder RidDlg.h"

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif

int G[26][32] =

{

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},

{0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1},

{0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1},

{0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1},

{0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1}

};

int H1[10][4][8] =

{

{

{0,1,2,3,4,5,6,7},

{8,9,10,11,12,13,14,15},

{16,17,18,19,20,21,22,23},

{24,25,26,27,28,29,30,31},

},

{

{0,1,2,3,8,9,10,11},

{4,5,6,7,12,13,14,15},

{16,17,18,19,24,25,26,27},

{20,21,22,23,28,29,30,31},

},

{

{0,1,4,5,8,9,12,13},

{2,3,6,7,10,11,14,15},

{16,17,20,21,24,25,28,29},

{18,19,22,23,26,27,30,31},

},

{

{0,2,4,6,8,10,12,14},

{1,3,5,7,9,11,13,15},

{16,18,20,22,24,26,28,30},

{17,19,21,23,25,27,29,31},

},

{

{0,1,2,3,16,17,18,19},

{4,5,6,7,20,21,22,23},

{8,9,10,11,24,25,26,27},

{12,13,14,15,28,29,30,31},

},

{

{2,3,6,7,18,19,22,23},

{0,1,4,5,16,17,20,21},

{8,9,12,13,24,25,28,29},

{10,11,14,15,26,27,30,31},

},

{

{0,2,4,6,16,18,20,22},

{1,3,5,7,17,19,21,23},

{8,10,12,14,24,26,28,30},

{9,11,13,15,25,27,29,31},

},

{

{0,1,8,9,16,17,24,25},

{2,3,10,11,18,19,26,27},

{4,5,12,13,20,21,28,29},

{6,7,14,15,22,23,30,31},

},

{

{0,2,8,10,16,18,24,26},

{1,3,9,11,17,19,25,27},

{4,6,12,14,20,22,28,30},

{5,7,13,15,21,23,29,31},

},

{

{0,4,8,12,16,20,24,28},

{1,5,9,13,17,21,25,29},

{2,6,10,14,18,22,26,30},

{3,7,11,15,19,23,27,31},

}

};

int H2[10][8][4] =

{

{

{0,1,2,3},

{4,5,6,7},

{8,9,10,11},

{12,13,14,15},

{16,17,18,19},

{20,21,22,23},

{24,25,26,27},

{28,29,30,31}

},

{

{0,1,4,5},

{2,3,6,7},

{8,9,12,13},

{10,11,14,15},

{16,17,20,21},

{18,19,22,23},

{24,25,28,29},

{26,27,30,31}

},

{

{0,2,4,6},

{1,3,5,7},

{8,10,12,14},

{9,11,13,15},

{16,18,20,22},

{17,19,21,23},

{24,26,28,30},

{25,27,29,31},

},

{

{0,1,8,9},

{2,3,10,11},

{4,5,12,13},

{6,7,14,15},

{16,17,24,25},

{18,19,26,27},

{20,21,28,29},

{22,23,30,31},

},

{

{0,2,8,10},

{1,3,9,11},

{4,6,12,14},

{5,7,13,15},

{16,18,24,26},

{17,19,25,27},

{20,22,28,30},

{21,23,29,31},

},

{

{0,4,8,12},

{1,5,9,13},

{2,6,10,14},

{3,7,11,15},

{16,20,24,28},

{17,21,25,29},

{18,22,26,30},

{19,23,27,31},

},

{

{0,1,16,17},

{2,3,18,19},

{4,5,20,21},

{6,7,22,23},

{8,9,24,25},

{10,11,26,27},

{12,13,28,29},

{14,15,30,31},

},

{

{0,2,16,18},

{1,3,17,19},

{4,6,20,22},

{5,7,21,23},

{8,10,24,26},

{9,11,25,27},

{12,14,28,30},

{13,15,29,31},

},

{

{0,4,16,20},

{1,5,17,21},

{2,6,18,22},

{3,7,19,23},

{8,12,24,28},

{9,13,25,29},

{10,14,26,30},

{11,15,27,31},

},

{

{0,8,16,24},

{1,9,17,25},

{2,10,18,26},

{3,11,19,27},

{4,12,20,28},

{5,13,21,29},

{6,14,22,30},

{7,15,23,31},

}

};

int H3[5][16][2]=

{

{

{0,1},

{2,3},

{4,5},

{6,7},

{8,9},

{10,11},

{12,13},

{14,15},

{16,17},

{18,19},

{20,21},

{22,23},

{24,25},

{26,27},

{28,29},

{30,31}

},

{

{0,2},

{1,3},

{4,6},

{5,7},

{8,10},

{9,11},

{12,14},

{13,15},

{16,18},

{17,19},

{20,22},

{21,23},

{24,26},

{25,27},

{28,30},

{29,31}

},

{

{0,4},

{1,5},

{2,6},

{3,7},

{8,12},

{9,13},

{10,14},

{11,15},

{16,20},

{17,21},

{18,22},

{19,23},

{24,28},

{25,29},

{26,30},

{27,31}

},

{

{0,8},

{1,9},

{2,10},

{3,11},

{4,12},

{5,13},

{6,14},

{7,15},

{16,24},

{17,25},

{18,26},

{19,27},

{20,28},

{21,29},

{22,30},

{23,31}

},

{

{0,16},

{1,17},

{2,18},

{3,19},

{4,20},

{5,21},

{6,22},

{7,23},

{8,24},

{9,25},

{10,26},

{11,27},

{12,28},

{13,29},

{14,30},

{15,31}

}

};

/////////////////////////////////////////////////////////////////////////////

// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog

{

public:

CAboutDlg();

// Dialog Data

//{{AFX_DATA(CAboutDlg)

enum { IDD = IDD_ABOUTBOX };

//}}AFX_DATA

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL(CAboutDlg)

protected:

virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support

//}}AFX_VIRTUAL

// Implementation

protected:

//{{AFX_MSG(CAboutDlg)

//}}AFX_MSG

DECLARE_MESSAGE_MAP()

};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)

{

//{{AFX_DATA_INIT(CAboutDlg)

//}}AFX_DATA_INIT

}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

//{{AFX_DATA_MAP(CAboutDlg)

//}}AFX_DATA_MAP

}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)

//{{AFX_MSG_MAP(CAboutDlg)

// No message handlers

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////

// CDecoderRidDlg dialog

CDecoderRidDlg::CDecoderRidDlg(CWnd* pParent /*=NULL*/)

: CDialog(CDecoderRidDlg::IDD, pParent)

{

//{{AFX_DATA_INIT(CDecoderRidDlg)

m_codestring = _T("");

m_decodeword = _T("");

//}}AFX_DATA_INIT

// Note that LoadIcon does not require a subsequent DestroyIcon in Win32

m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

}

void CDecoderRidDlg::DoDataExchange(CDataExchange* pDX)

{

CDialog::DoDataExchange(pDX);

//{{AFX_DATA_MAP(CDecoderRidDlg)

DDX_Text(pDX, IDC_CODEWORD, m_codestring);

DDV_MaxChars(pDX, m_codestring, 32);

DDX_Text(pDX, IDC_DECODERWORD, m_decodeword);

DDV_MaxChars(pDX, m_decodeword, 26);

//}}AFX_DATA_MAP

}

BEGIN_MESSAGE_MAP(CDecoderRidDlg, CDialog)

//{{AFX_MSG_MAP(CDecoderRidDlg)

ON_WM_SYSCOMMAND()

ON_WM_PAINT()

ON_WM_QUERYDRAGICON()

ON_EN_CHANGE(IDC_CODEWORD, OnChangeCodeword)

ON_BN_CLICKED(IDDECODER, OnDecoder)

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////

// CDecoderRidDlg message handlers

BOOL CDecoderRidDlg::OnInitDialog()

{

CDialog::OnInitDialog();

// Add "About..." menu item to system menu.

// IDM_ABOUTBOX must be in the system command range.

ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);

ASSERT(IDM_ABOUTBOX < 0xF000);

CMenu* pSysMenu = GetSystemMenu(FALSE);

if (pSysMenu != NULL)

{

CString strAboutMenu;

strAboutMenu.LoadString(IDS_ABOUTBOX);

if (!strAboutMenu.IsEmpty())

{

pSysMenu->AppendMenu(MF_SEPARATOR);

pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);

}

}

// Set the icon for this dialog. The framework does this automatically

// when the application's main window is not a dialog

SetIcon(m_hIcon, TRUE); // Set big icon

SetIcon(m_hIcon, FALSE); // Set small icon

Init();

return TRUE; // return TRUE unless you set the focus to a control

}

void CDecoderRidDlg::OnSysCommand(UINT nID, LPARAM lParam)

{

if ((nID & 0xFFF0) == IDM_ABOUTBOX)

{

CAboutDlg dlgAbout;

dlgAbout.DoModal();

}

else

{

CDialog::OnSysCommand(nID, lParam);

}

}

// If you add a minimize button to your dialog, you will need the code below

// to draw the icon. For MFC applications using the document/view model,

// this is automatically done for you by the framework.

void CDecoderRidDlg::OnPaint()

{

if (IsIconic())

{

CPaintDC dc(this); // device context for painting

SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

// Center icon in client rectangle

int cxIcon = GetSystemMetrics(SM_CXICON);

int cyIcon = GetSystemMetrics(SM_CYICON);

CRect rect;

GetClientRect(&rect);

int x = (rect.Width() - cxIcon + 1) / 2;

int y = (rect.Height() - cyIcon + 1) / 2;

// Draw the icon

dc.DrawIcon(x, y, m_hIcon);

}

else

{

CDialog::OnPaint();

}

}

// The system calls this to obtain the cursor to display while the user drags

// the minimized window.

HCURSOR CDecoderRidDlg::OnQueryDragIcon()

{

return (HCURSOR) m_hIcon;

}

void CDecoderRidDlg::OnChangeCodeword()

{

UpdateData(TRUE);

for(int i = 0; i < m_codestring.GetLength(); i++)

if(m_codestring[i] != '1')

if(m_codestring[i] != '0')

{

char bufer[100];

sprintf(bufer, "%d-e neiaie aaaaai ia i?aaeeuii", i+1);

MessageBox(bufer);

m_codestring.Delete(i);

}

UpdateData(FALSE);

}

void CDecoderRidDlg::OnDecoder()

{

int i = 0;

int k = 0;

if(m_codestring.GetLength() < 32)

{

MessageBox("Aaaaaiu ia ana neiaieu, iaaaaaaiiua neiaieu n?eoa?ony 0");

for(i = m_codestring.GetLength() - 1; i < 31; i++)

m_codestring += '0';

}

for(i = 0; i < 32; i++)

{

if(m_codestring[i] == '0')

codword[i] = 0;

else

codword[i] = 1;

}

int sum1[4] = {0,0,0,0};

for(i = 9, k = 0; i >= 0; i--, k++)

{

for(int j = 0; j < 4; j++)

{

sum1[j] = codword[H1[k][j][0]] + codword[H1[k][j][1]] +

codword[H1[k][j][2]] + codword[H1[k][j][3]] +

codword[H1[k][j][4]] + codword[H1[k][j][5]] +

codword[H1[k][j][6]] + codword[H1[k][j][7]];

sum1[j] %= 2;

}

decordword[16+i] = Majorit4(sum1[0]+sum1[1]+sum1[2]+sum1[3]);

}

DecrementR3();

int sum2[8] = {0,0,0,0,0,0,0,0};

for(i = 9, k = 0; i >= 0; i--, k++)

{

for(int j = 0; j < 8; j++)

{

sum2[j] = codword[H2[k][j][0]] + codword[H2[k][j][1]] +

codword[H2[k][j][2]] + codword[H2[k][j][3]];

sum2[j] %= 2;

}

decordword[6+i] = Majorit8(sum2[0]+sum2[1]+sum2[2]+sum2[3]+

sum2[4]+sum2[5]+sum2[6]+sum2[7]);

}

DecrementR2();

int sum3[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

for(i = 5, k = 0; i >= 1; i--, k++)

{

for(int j = 0; j < 16; j++)

{

sum3[j] = codword[H3[k][j][0]] + codword[H3[k][j][1]];

sum3[j] %= 2;

}

decordword[i] = Majorit16(sum3[0]+sum3[1]+sum3[2]+sum2[3]+sum3[4]+

sum3[5]+sum3[6]+sum3[7]+sum3[8]+sum3[9]+

sum3[10]+sum2[11]+sum3[12]+sum3[13]+

sum3[14]+sum3[15]);

}

DecrementR1();

int sum4 = 0;

for(i = 0; i < 32; i++)

sum4 += codword[i];

decordword[0] = Majorit32(sum4);

m_decodeword.Empty();

for(i = 0; i < 26; i++)

{

if(decordword[i] == 1)

m_decodeword += '1';