XXIV Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

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

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Сорокин А.Д. 1

---

1ГБОУ "Школа №1526 на Покровской"

Ивкина Е.С. 1

---

1ГБОУ "Школа №1526 на Покровской"

Работа в формате PDF

432.9 KB

Автор работы награжден дипломом победителя II степени

Диплом школьникаСвидетельство руководителя

Проблема

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

2. ЦЕЛЬ

Цель:

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

В качестве исходных данных будут использоваться:

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

2. Вероятность одиночной ошибки в канале связи, по которому передается информация.

По каждому коду должен быть рассчитан ряд параметров:

• Длина кодового слова – количество символов в одном кодовом слове

• Количество информационных символов – количество символов, в которых закодирована передаваемая информация. Эти символы зависят только от передаваемой информации

• Количество проверочных символов – дополнительные символы, которые формируются по определенным правилам из информационных.

• Ёмкость кода – наибольшее количество разных кодовых комбинаций

• Избыточность кода – коэффициент, определяющий, насколько число элементов в символе кода больше, чем это требовалось бы при полном их использовании.

• Вероятность появления обнаруживаемой ошибки – вероятность того, что при передаче кодовой последовательности в ней произойдет ошибка, которая будет обнаружена «приемником».

• Вероятность появления необнаруживаемой ошибки – вероятность того, что при передаче кодовой последовательности в ней произойдет ошибка, которая не будет обнаружена «приемником»

• Общая вероятность всех возможных ошибок – вероятность появления при передаче информации всех возможных ошибок (как обнаруживаемых, так и не обнаруживаемых)

• Коэффициент вероятность обнаружения ошибки – отношение вероятность обнаруживаемых ошибок к вероятности любой ошибки, выраженная в процентах.

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

3. Задача

Задачи:

1. Изучить все перечисленные коды:

   1. Формирование кодовой последовательности

   2. Формулы для расчета основных показателей кода

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

3. Объединить все программы в одну.

4. Протестировать программу.

Ограничения:

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

• Код с постоянным весом

• Код с проверкой на четность

• Код с двумя проверками на четность

• Код с повторением

• Инверсивный код

• Корреляционный код

• Код Бергера

4. Решение поставленной задачи

1. 1. Код постоянного веса

1. 1. 1. Описание кода

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

На принимающей стороне выполняется проверка каждой кодовой последовательности на значение веса кода:

• если количество единиц будет отличаться от веса кода – кодовая последовательность отклоняется,

• если соответствует весу кода – принимается.

Принимающая сторона может пропустить сообщение с ошибкой, если произошло, например, произошло повреждение сразу двух символов: один «0» изменился на «1», а одна «1» изменилась на «0».

1. 1. 2. Параметры кода

Основные параметры кода и формулы для их вычисления представлены в таблице (Таблица 1).

Таблица 1. Параметры кода постоянного веса

1. 1. 3. Пример формирования кода

В качестве примера рассмотрен код постоянного веса с общей длиной кодового слова – 5, и весом – 3 ( ). Емкость такого кода равна

На рисунке (Рисунок 1) приведен пример всех возможных кодовых комбинаций для кода .

Рисунок 1 Кодовые комбинации для кода постоянного веса

1. 1. 4. Блок-схема программы

Блок-схема программы для кода постоянного веса представлена на рисунке (Рисунок 2).

Рисунок 2 Блок-схема для кода постоянного веса

1. 1. 5. Контрольный пример

Исходные данные:

• количество разных символов, которые должны передаваться: 16

• вероятность одиночной ошибки в канале связи: 0.001

Результаты работы программы (Рисунок 3):

Рисунок 3 Результаты расчета для кода постоянного веса

1. 2. Код с проверкой на четность

1. 1. 1. Описание кода

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

На принимающей стороне суммируются «по модулю два» все символы полученной кодовой последовательности:

• если сумма равна «1» – кодовая последовательность отклоняется,

• если сумма равна «0» – принимается.

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

1. 1. 2. Параметры кода

Основные параметры кода и формулы для их вычисления представлены в таблице (Таблица 2).

Таблица 2. Параметры кода с проверкой на четность

1. 1. 3. Пример формирования кода

В качестве примера рассмотрен код с 3-мя информационными разрядами.
Емкость такого кода равна

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

Рисунок 4 Кодовые комбинации для кода с проверкой на четность (k=3)

1. 1. 4. Блок-схема программы

Блок-схема программы для кода с проверкой на чётность представлена на рисунке (Рисунок 2).

Рисунок 5 Блок-схема для кода с проверкой на четность

1. 1. 5. Контрольный пример

Исходные данные:

• количество разных символов, которые должны передаваться: 16

• вероятность одиночной ошибки в канале связи: 0.001

Результаты работы программы (Рисунок 6):

Рисунок 6 Результаты расчета для кода с проверкой на четность

1. 3. Код с двумя проверками на четность

1. 1. 1. Описание кода

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

• первый содержит сумму «по модулю два» всех разрядов основной кодовой последовательности.

• второй – сумму «по модулю два» только нечетных разрядов основной кодовой последовательности

На принимающей стороне проверка происходит в два этапа: суммируются «по модулю два» все символы информационных разрядов и первый проверочный разряд; суммируются «по модулю два» символы всех нечетных информационных разрядов и второй проверочный разряд.

• если сумма хотя бы в одной из проверок равна «1» – кодовая последовательность отклоняется,

• если обе суммы равны «0» – принимается.

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

1. 1. 2. Параметры кода

Основные параметры кода и формулы для их вычисления представлены в таблице (Таблица 3).

Таблица 3. Параметры кода с двойной проверкой на четность

1. 1. 3. Пример формирования кода

В качестве примера рассмотрен код с 3-мя информационными разрядами.
Емкость такого кода равна

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

Рисунок 7 Кодовые комбинации для кода с двойной проверкой на четность (k=3)

1. 1. 4. Блок-схема программы

Блок-схема программы для кода с двойной проверкой на чётность представлена на рисунке (Рисунок 8).

Рисунок 8 Блок-схема для кода с двойной проверкой на четность

1. 1. 5. Контрольный пример

Исходные данные:

• количество разных символов, которые должны передаваться: 16

• вероятность одиночной ошибки в канале связи: 0.001

Результаты работы программы (Рисунок 9):

Рисунок 9 Результаты расчета для кода с двойной проверкой на четность

1. 4. Код с повторением

1. 1. 1. Описание кода

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

На принимающей стороне происходит попарное сравнение всех символов в информационной и проверочной (дублирующей).

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

• если все значения совпали – принимается.

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

1. 1. 2. Параметры кода

Основные параметры кода и формулы для их вычисления представлены в таблице (Таблица 4).

Таблица 4. Параметры кода с повторением

1. 1. 3. Пример формирования кода

В качестве примера рассмотрен код с 3-мя информационными разрядами.
Емкость такого кода равна

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

Рисунок 10 Кодовые комбинации для кода с повторением (k=3)

1. 1. 4. Блок-схема программы

Блок-схема программы для кода с повторением представлена на рисунке (Рисунок 11).

Рисунок 11 Блок-схема для кода с повторением

1. 1. 5. Контрольный пример

Исходные данные:

• количество разных символов, которые должны передаваться: 16

• вероятность одиночной ошибки в канале связи: 0.001

Результаты работы программы (Рисунок 12):

Рисунок 12 Результаты расчета для кода с повторением

1. 5. Инверсивный код (код Бауэра)

1. 1. 1. Описание кода

Количество проверочных символов в инверсивном коде равно количеству информационных символов. Проверочные разряды формируются по следующему правилу:

• Если количество единиц в информационных разрядах четное, то проверочные разряды дублируют информационные

• Если количество единиц в информационных разрядах нечетное, то проверочные разряды формируются, как инверсия информационных

На принимающей стороне проверка производится в два этапа:

• На первом этапе определяется четное или нечетное количество единиц в информационных разрядах.

• На втором этапе, в зависимости от определенного количества единиц, значения информационных разрядов сравниваются на соответствие с проверочными разрядами.

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

1. 1. 2. Параметры кода

Основные параметры инверсивного кода и формулы для их вычисления представлены в таблице (Таблица 5).

Таблица 5. Параметры инверсивного кода

1. 1. 3. Пример формирования кода

В качестве примера рассмотрен код с 3-мя информационными разрядами.
Емкость такого кода равна

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

Рисунок 13 Кодовые комбинации для инверсивного кода (k=3)

1. 1. 4. Блок-схема программы

Блок-схема программы для инверсивного кода представлена на рисунке (Рисунок 14).

Рисунок 14 Блок-схема для инверсивного кода

1. 1. 5. Контрольный пример

Исходные данные:

• количество разных символов, которые должны передаваться: 16

• вероятность одиночной ошибки в канале связи: 0.001

Результаты работы программы (Рисунок 15):

Рисунок 15 Результаты расчета для инверсивного кода

1. 6. Корреляционный код

1. 1. 1. Описание кода

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

• 0 -> 01

• 1 -> 10

На принимающей стороне последовательность преобразуется в обратном порядке, и последовательность не принимается, если в парных разрядах будет обнаружено сочетание «00» или «11».

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

1. 1. 2. Параметры кода

Основные параметры инверсивного кода и формулы для их вычисления представлены в таблице (Таблица 6).

Таблица 6. Параметры корреляционного кода

1. 1. 3. Пример формирования кода

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

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

Рисунок 16 Кодовые комбинации для корреляционного кода (k=3)

1. 1. 4. Блок-схема программы

Блок-схема программы для корреляционного кода представлена на рисунке (Рисунок 17).

Рисунок 17 Блок-схема для корреляционного кода

1. 1. 5. Контрольный пример

Исходные данные:

• количество разных символов, которые должны передаваться: 16

• вероятность одиночной ошибки в канале связи: 0.001

Результаты работы программы (Рисунок 18):

Рисунок 18 Результаты расчета для корреляционного кода

1. 7. Код Бергера

1. 1. 1. Описание кода

Проверочные разряды в коде Бергера – это количество единиц в информационных разрядах, представленных в двоичной системе счисления.

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

На принимающей стороне проверка производится в два этапа:

• По проверочным разрядам определяется количество единиц.

• Подсчитывается количество единиц в информационных разрядах и сравнивается с данными проверочных разрядок.

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

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

1. 1. 2. Параметры кода

Основные параметры кода Бергера и формулы для их вычисления представлены в таблице (Таблица 5).

Таблица 7. Параметры кода Бергера

1. 1. 3. Пример формирования кода

В качестве примера рассмотрен код с 3-мя информационными разрядами.
Емкость такого кода равна .
Максимальное количество единиц, которое может содержать такая кодовая последовательность, равно 3 (111), в двоичной системе счисления 3 -> 11, следовательно количество проверочных разрядов для такого кода равно 2.

Н а рисунке (Рисунок 19) приведен пример всех возможных кодовых комбинаций для такого кода Бергера.

Рисунок 19 Кодовые комбинации для Кода Бергера (k=3)

1. 1. 4. Блок-схема программы

Блок-схема программы для кода Бергера представлена на рисунке (Рисунок 20).

Рисунок 20 Блок-схема для кода Бергера

1. 1. 5. Контрольный пример

Исходные данные:

• количество разных символов, которые должны передаваться: 16

• вероятность одиночной ошибки в канале связи: 0.001

Результаты работы программы (Рисунок 21):

Рисунок 21 Результаты расчета для кода Бергера

5. Тестирование

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

• Количество различных состояний/символов, которые требуется передать с использованием кода

• Вероятность одиночной ошибки в канале связи, по которому передается информация.

Было проведено тестирование общей программы. Программа работоспособная и позволяет быстро рассчитывать все параметры семи предложенных кодов на основании исходных данных.

Результаты работы программы представлены в виде списка параметров для каждого кода, также основные параметры выведены в таблицу (Рисунок 22).

Рисунок 22 Результаты расчета в табличном виде

6. ИТОГИ И ВЫВОДЫ

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

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

• Количество различных состояний/символов, которые требуется передать с использованием кода

• Вероятность одиночной ошибки в канале связи, по которому передается информация.

Программа рассчитывает параметры для семи кодов:

• Код с постоянным весом

• Код с проверкой на четность

• Код с двумя проверками на четность

• Код с повторением

• Инверсивный код

• Корреляционный код

• Код Бергера

В качестве выходных данных для каждого из семи предложенных кодов определяются:

• Длина кодового слова

• Ёмкость кода

• Избыточность

• Вероятность необнаруженных ошибок

• Вероятность любых ошибок

• Вероятность обнаруживаемых ошибок

• Коэффициент обнаружения ошибок

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

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

Список используемой литературы

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

2. Тутевич В.Н. Телемеханика. – М.: Высш.шк., 1985. – 423 с.

3. Баранов Л.А., Ерофеев Е.В., Астрахан В.И. и др,. Системы автоматического и телемеханического управления электроподвижным составом. М.: Транспорт, 1983. – 311 с.