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

Лабораторная работа №1 по курсу «Цифровая связь».

Введение

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

Автоматический запрос повторной передачи

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

Существует несколько процедур ARQ:
  1. Запрос с остановками (stop-and-wait ARQ) (Рисунок 1а). Данной процедуре ARQ достаточно полудуплексного соединения, поскольку передатчик перед началом очередной передачи ожидает подтверждения об успешном приеме (acknowledgement – ACK) предыдущей. В примере, приведенном на рисунке, третий блок передаваемых данных принят с ошибкой. Следовательно, приемник передает отрицательные подтверждения приема (negative acknowledgement – NAK), передатчик повторяет третий блок сообщения и только после этого передает следующий по очередности блок.
  2. Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback) (Рисунок 1б). Данная процедура ARQ требует полнодуплексное соединение. Оба оконечных устройства начинают передачу одновременно: передатчик отправляет информацию, а приемник передает подтверждение о приеме данных. Каждому блоку передаваемых данных присваивается порядковый номер. Кроме того, номера кадров ACK и NAK должны быть согласованы, то есть задержка распространения сигнала должна быть известна заранее, чтобы передатчик знал, к какому блоку сообщения относится данный кадр подтверждения приема. В примере (Рисунок 1б) время подобрано так, что между отправленным блоком сообщений и полученным подтверждением о приеме существует постоянный интервал в четыре блока. При использовании процедуры ARQ передатчик «возвращается» к сообщению с ошибкой и снова передает всю информацию, начиная с поврежденного сообщения.
  3. Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat) (Рисунок 1в). Данная процедура ARQ требует полнодуплексное соединение. В этой процедуре повторно передается только искаженное сообщение, затем передатчик продолжает передачу с того места, где она прервалась, не выполняя повторной передачи правильно принятых сообщений.
Выбор типа процедуры ARQ является компромиссом между требованиями эффективности применения ресурсов связи и необходимостью полнодуплексной связи.

Рисунок 1. Автоматический запрос повторной передачи (ARQ): а) запрос ARQ с остановками (полудуплексная связь), б) непрерывный запрос ARQ с возвратом (полнодуплексная связь), в) непрерывный запрос ARQ с выборочным повторением (полнодуплексная связь).

Главное преимущество схем ARQ перед схемами прямого исправления ошибок (forward error correction) заключается в том, что обнаружение ошибок требует гораздо более простого декодера и меньшей избыточности. Кроме того, она более гибкая: информация передается только при обнаружении ошибки. Ключевым элементом процедуры ARQ является механизм детектирования ошибок, который требует использования циклических блочных кодов.

Циклические блочные коды

При использовании блочных кодов передаваемые данные делятся на блоки из k бит, каждый из блоков называют сообщением. В процессе кодирования каждый k-битовый блок данных преобразуется в больший блок из n бит, который называется кодовым битом или канальным символом. К каждому блоку данных кодирующее устройство прибавляет (n – k) бит, которые называются избыточными битами (redundant bits), битами четности (parity bits) или контрольными битами (check bits), которые не несут новой информации. Для обозначения описанного кода используется запись (n, k). Отношение числа избыточных бит к числу информационных бит, (n – k)/k, называется избыточностью (redundancy) кода, отношение числа бит данных к общему числу бит, k/n, именуется кодовой скоростью или степенью кодирования (coding rate).

Важным подклассом линейных блочных кодов являются двоичные циклические коды (cyclic codes). Код легко реализуется на регистре сдвига с обратной связью. Линейный (n, k)-код называется циклическим, если в результате циклического сдвига кодового слова U = (u0, u1, …, un–1) получается другое кодовое слово данного кода U1 = (un–1, u0, u1, …, un–2). Компоненты кодового слова возможно рассматривать как коэффициенты полинома:

Информационное сообщение:

Полиномиальный генератор:

В кодовых словах, выраженных в полиномиальной форме, циклическая природа кода проявляется следующим образом: если U(X) является кодовым словом, представленным полиномом порядка (n – 1), то Ui(X) – остаток от деления XiU(X) на Xn + 1 – также является кодовым словом. То есть:

или, умножая обе части уравнения на Xn + 1:

что в модульной арифметике возможно записать следующим образом:

где x mod y означает остаток от деления x на y.

Процедура кодирования в несистематической форме описывается выражением:

таким образом k = n – p. Тогда:

Полиномиальный генератор g(X) циклического кода (n, k) является множителем Xn + 1, т.е. (Xn + 1)h(X) = g(X).

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

Систематический блочный код

Для формирования кодового слова U(X) необходимо сдвинуть информационные биты m(X) на (n – k) бит вправо:

и добавить в левые разряды биты четности p(X). Кодовое слово:

Здесь p(X) возможно записать как:

Передаваемое кодовое слово искажается помехами. Допустим, что передается кодовое слово U(X), а принимается Z(X) = U(X) + e(X), где e(X) – модель полинома ошибки. Декодер проверяет, является ли Z(X) полиномом кодового слова, т.е. делится ли он на g(X) без остатка. Это осуществляется путем вычисления синдрома принятого полинома. Синдром S(X) равен остатку от деления Z(X) на g(X):

Синдром кодового слова равен синдрому ошибки:

Логические схемы для систематического кодирования и обнаружения ошибок

Основную операцию при кодировании выполняет полиномиальный делитель. Структура кодера представлена на рисунке (Рисунок 2).

Рисунок 2. Систематический кодер линейного блочного циклического кода.

Кодер функционирует следующим образом:
  1. При первых k сдвигах ключ 1 закрыт для передачи битов сообщения в (n – k)-разрядный регистр сдвига.
  2. Ключ 2 уставлен в нижнее положение для битов сообщения на выходной регистр в течение первых k сдвигов.
  3. После передачи k-го бита сообщения ключ 1 открывается, а ключ 2 переходит в верхнее положение.
  4. При остальных (n – k) сдвигах происходит очищение кодирующих регистров, биты четности перемещаются в выходной регистр.
  5. Общее число сдвигов равно n, и содержимое выходного регистра представляет собой полином кодового слова.
Расчет синдрома выполняется с помощью схемы деления, аналогичной схеме систематического кодирования (Рисунок 3). Если вектор синдрома нулевой, считается, что принятый вектор является правильным кодовым словом, иначе принятый вектор – это искаженное кодовое слово.

Рисунок 3. Схема вычисления синдрома.

Передаваемое кодовое слово искажается помехами. Допустим, что передается кодовое слово U(X), а принимается Z(X) = U(X) + e(X), где e(X) – модель полинома ошибки. Декодер проверяет, является ли Z(X) полиномом кодового слова, т.е. делится ли он на g(X) без остатка. Это осуществляется путем вычисления синдрома принятого полинома. Синдром S(X) равен остатку от деления Z(X) на g(X):

Синдром кодового слова равен синдрому ошибки:

Коды CRC

Примером использования циклических кодов является контроль ошибок с помощью циклического избыточного CRC кода (Cyclic Redundancy Check), называемого также кодом Абрамсона. При передаче данных в пакетных режимах, эти коды используются для определения целостности блоков данных (FCS – Frame Checking Sequence). CRC коды часто представляют собой расширения циклических кодов Хэмминга. Выбор полинома g(X) зависит от допустимой вероятности необнаруженной ошибки, которая определяется распределением (спектром) весов кода.

Пример расчета CRC кода с составлением логической схемы

Рассматривается CRC-код со следующим набором параметров:
  • Название алгоритма (Alg): CRC-6-GSM.
  • Полиномиальный генератор (g(X)): 0x2F.
  • Инициализирующее значение регистров (Init): 0x00.
  • Флаг, указывающий, инвертируется ли порядок битов сообщения при входе в регистры (RefIn): false.
  • Флаг, указывающий, инвертируется ли порядок битов регистра при выходе (RefOut): false.
  • Число, с которым складывается по модулю 2 проверочные биты (XorOut): 0x3F.
  • Значение CRC для строки ASCII «123456789» (Check): 0x13.

Для получения полиномиальной формы записи g(X) необходимо преобразовать число 0x2F к двоичному вектору 1011112, что соответствует полиному:

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

Следует преобразовать необходимые для создания модели параметры в двоичную форму: XorOut = 1111112; Check = 0100112.

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

Рисунок 4. Кодер систематического двоичного CRC кода

Полиномиальный генератор имеет вид g(X) = 1 + X + X2 + X3 + X5 + X6, что соответствует расположению операций сложения по модулю 2 в цепи обратной связи (отсутствует связь, соответствующая X4).

На выходе регистра производится сложение по модулю 2 проверочных битов с единицей, поскольку XorOut = 1111112 (необходимо сложить с 1 каждый проверочный бит).

Схема вычисления синдрома представлена на рисунке (Рисунок 5).

Рисунок 5. Схема расчета синдрома систематического двоичного CRC кода

В том случае, если параметры RefIn и/или RefOut принимают значение «true» схема кодирования и вычисления синдрома усложнятся: необходимо добавить регистры LIFO на входах и выходах схем. Операция обращения предполагает изменение порядка следования информационных бит с прямого на обратный (RefIn) или проверочных бит (RefOut) аналогичным образом.

Цель работы:

Задачи работы:

Выполнение лабораторной работы

Содержание лабораторной работы

В ходе выполнения данной лабораторной работы будет:
  • создан новый проект;
  • продемонстрирован процесс установки блоков на схему и их соединения между собой;
  • продемонстрирован процесс задания свойств блоков;
  • проведено моделирование передачи данных через канал связи.

Создание нового проекта

Необходимо создать новый проект, для этого:
  1. В главном окне SimInTech нажать кнопку «Файл» и выбрать пункт «Новый проект».
  2. В выпадающем меню выбрать пункт «Схема модели общего вида» (Рисунок 6).

    Рисунок 6. Главное окно SimInTech c выделенным меню создания нового проекта

Откроется новое окно проекта «Схема модели общего вида», в котором производится разработка моделей (Рисунок 7).

Рисунок 7. Окно проекта «Схема модели общего вида»

Требуется сохранить созданный проект. Для этого:
  1. В главном окне SimInTech нажать кнопку «Файл» и выбрать пункт «Сохранить проект как...».
  2. В появившемся окне выбрать или при необходимости создать папку, в которую будет сохранен данный проект.
  3. В поле «Имя файла» указать желаемое имя проекта либо оставить имя проекта по умолчанию и нажать на кнопку «Сохранить».

Задание глобальных констант

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

Необходимо открыть окно редактора скрипта проекта одинарным нажатием левой кнопкой мыши по кнопке «Скрипт», расположенной на панели кнопок окна проекта (Рисунок 8).

Рисунок 8. Окно проекта с выделенной кнопкой «Скрипт».

Откроется окно «Скрипт станицы» (Рисунок 9).

Рисунок 9. Окно «Скрипт страницы».

В окне «Скрипт страницы» требуется задать код согласно рисунку, а затем нажать на кнопку «Закрыть и применить», чтобы сохранить внесенные изменения (Рисунок 10).

Рисунок 10. Окно «Скрипт страницы» с добавленным кодом и выделенной кнопкой «Закрыть и применить».

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

Разработка модели кодера

Необходимо разработать модель CRC-кодера с полиномиальным генератором кода:

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

Добавление блоков на схему

Требуется добавить на схему блок «Субмодель» из вкладки «Субструктуры». Внутри данного блока будет сформирована модель кодера. Для добавления блока на схему необходимо выполнить следующие действия:
  1. В главном окне SimInTech в палитре блоков выбрать вкладку «Субструктуры» (Рисунок 11).

    Рисунок 11. Главное окно SimInTech с выбранной вкладкой «Субструктуры» в палитре блоков.

  2. Одинарным нажатием левой кнопкой мыши выбрать блок «Субмодель».
  3. Перевести курсор мыши на рабочую область проекта. В рабочей области появится графическое изображение блока «Субмодель», которое будет следовать за указателем мыши.
  4. В рабочей области окна проекта выбрать место для установки блока и установить блок одинарным нажатием левой кнопкой мыши (Рисунок 12).

    Рисунок 12. Окно проекта с добавленным блоком «Субмодель».

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

Необходимо задать подпись блоку «Субмодель», для этого:
  1. Выделить на схеме блок «Субмодель» одинарным нажатием левой кнопкой мыши по нему (Рисунок 13).

    Рисунок 13. Окно проекта с выделенным блоком «Субмодель».

  2. Открыть область подписи блока двойным нажатием левой кнопкой мыши на прямоугольную область, расположенную рядом с выделенным блоком, и задать подпись «Кодер».
  3. Для того, чтобы переместить поле подписи блока, необходимо нажать левой кнопкой мыши на красный прямоугольник в верхней части этого поля и переместить его, не отпуская левую кнопку мыши.
Двойным нажатием по блоку «Субмодель» необходимо зайти в субмодель. В окне проекта откроется рабочая область блока «Субмодель» (Рисунок 14).

Рисунок 14. Рабочая область блока «Субмодель».

Необходимо добавить в рабочую область субмодели и разместить, согласно рисунку (Рисунок 15), следующие блоки:
  • 2 блока «Константа», 1 блок «Меандр» и 1 блок «Генератор единичных импульсов» из вкладки «Источники». Данные блоки будут формировать сигналы, необходимые для функционирования кодера.
  • 1 блок «Порт входа» и 1 блок «Порт выхода» из вкладки «Субструктуры». Данные блоки необходимы для приема и передачи данных через порты блока «Субмодель».
  • 2 блока «Ключ управляемый перекидной по входам тип 1» из вкладки «Ключи». Данные блоки необходимы для коммутации сигналов кодера.
  • 6 блоков «Логические операции» из вкладки «Логические». Данные блоки необходимы для реализации обратной связи и инвертирования проверочных бит.
  • 6 блоков «Запаздывание на период квантования» из вкладки «Дискретные». Данные блоки будут моделировать сдвиговые регистры.

Рисунок 15. Окно проекта с добавленными блоками.

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

Задание свойств блоков

Модель кодера содержит ключи, которые должны переключаться после передачи информационных бит сообщения. Необходимо сформировать сигнал, который будет равен «1» в течение передачи информационных бит и равен «0» в течение передачи проверочных бит. Для этого следует задать свойства блока «Меандр»:
  1. Одинарным нажатием левой кнопкой мыши выделить блок «Меандр»
  2. Одинарным нажатием правой кнопкой мыши по выделенному блоку вызвать контекстное меню блока и в нем выбрать пункт «Свойства объекта» (Рисунок 16).

    Рисунок 16. Окно проекта с пунктом «Свойства объекта», выбранным в контекстном меню блока.

  3. Откроется окно «Свойства», в котором задаются свойства блока (Рисунок 17).

    Рисунок 17. Окно «Свойства» блока «Меандр» со свойствами по умолчанию.

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

    Рисунок 18. Окно «Свойства» блока «Меандр» с заданными для свойств формулами.

Блоки «Запаздывание на период квантования» будут моделировать сдвиговые регистры кодера. Информационный бит должен задерживаться в регистре на 1 период передачи. Также, после завершения кодирования следует сбросить значения, содержащиеся в регистрах, чтобы они не повлияли на кодирование следующего информационного сообщения. Для всех блоков «Запаздывание на период квантования» для свойства «Период квантования» необходимо задать формулу «T» и активировать пункт «Добавить порт сброса».

Следует сформировать сигнал сброса, который будет равен «1» в момент времени перед началом кодирования нового информационного сообщения. Для блока «Генератор единичных импульсов» для свойства «Период, с» требуется задать формулу «N * T».

В алгоритме кодирования используются операции «XOR», поэтому для каждого блока «Логические операции» требуется открыть окно свойств, в поле «Значение» свойства «Тип операнда» открыть список доступных операций и выбрать «(ИСКЛЮЧАЮЩЕЕ ИЛИ, XOR)».

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

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

Соединение блоков на схеме

Необходимо соединить блоки линиями связи, для этого:
  1. Навести курсор мыши на выходной порт блока «Меандр» (курсор мыши изменится на вертикальную стрелку) и нажать левую кнопку мыши.
  2. Появившуюся линию соединить с верхним входным портом любого из двух блоков «Ключ управляемый перекидной по входам тип 1» и нажать левую кнопку мыши.
После выполнения этих действий появится линия связи. Необходимо соединить блоки на схеме согласно рисунку (Рисунок 19).

Рисунок 19. Окно проекта с соединенными блоками.

Разработка модели CRC-кодера завершена. Необходимо выйти из рабочей области субмодели одинарным нажатием левой кнопкой мыши по кнопке «Возврат из субмодели» на панели кнопок окна проекта (Рисунок 20).

Рисунок 20. Окно проекта с выделенной кнопкой «Возврат из субмодели».

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

Проверка работы кодера

Следует проверить корректность работы кодера. Для этого необходимо подать на него информационное сообщение, для которого заранее известна последовательность проверочных бит, например, текстовое сообщение ASCII «123456789», которому соответствует последовательность проверочных бит «010011». В двоичном представлении сообщение содержит 72 информационных бита (по 8 бит на каждый символ ASCII).

Требуется добавить на схему 1 блок «Кусочно постоянная» из вкладки «Источники» и 1 блок «Временной график» из вкладки «Вывод данных», разместить блоки на схеме и соединить линиями связи согласно рисунку (Рисунок 21).

Рисунок 21. Окно проекта с соединенными блоками.

Блок «Кусочно постоянная» должен формировать информационные биты сообщения на каждом шаге моделирования. Для данного блока необходимо:

  • В поле «Формула» свойства «Массив временных интервалов» задать формулу «72#T». Данная формула формирует массив из 72 элементов, равных значению глобальной константы «T». После задания формулы произойдет автоматическое вычисление значения свойства в поле «Значение».
  • В поле «Формула» свойства «Массив значений» задать «[0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 1]». Данная последовательность бит соответствует передаваемому сообщению, описанному выше.

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

Настройка параметров расчета

Перед запуском моделирования необходимо настроить параметры расчета. Для этого в окне проекта на панели кнопок следует нажать на кнопку «Параметры расчета» (Рисунок 22).

Рисунок 22. Окно проекта с выделенной кнопкой «Параметры расчета».

В появившемся окне параметров проекта на вкладке «Параметры расчета» задать формулы для вычисления значений параметров «Минимальный шаг», «Максимальный шаг» и «Конечное время расчета»(Рисунок 23):
  • «Минимальный шаг» – «T».
  • «Максимальный шаг» – «T».
  • «Конечное время расчета» – «N * W * T».

Рисунок 23. Вкладка «Параметры расчета» окна «Параметры проекта».

Закрыть окно «Параметры расчета», при этом внесенные изменения будут сохранены автоматически.

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

Моделирование процесса кодирования

Необходимо запустить моделирование одинарным нажатием левой кнопкой мыши по кнопке «Пуск», расположенной на панели кнопок окна проекта (Рисунок 24).

Рисунок 24. Окно проекта с выделенной кнопкой «Пуск».

После завершения процесса моделирования необходимо открыть окно графика двойным нажатием левой кнопкой мыши по блоку «Временной график», а затем настроить параметры отображения результатов моделирования. Для этого следует вызвать контекстное меню одинарным нажатием правой кнопкой мыши по окну графика и выбрать пункт «Свойства» (Рисунок 25).

Рисунок 25. Контекстное меню окна «График».

В открывшемся окне свойств необходимо задать значение параметра «Шаг сетки» для оси X равным «0.4», активировать параметр «Ступенчатый» и нажать кнопку «Ok» (Рисунок 26).

Рисунок 26. Окно «Свойства графика» с измененными значениями свойств.

Для наглядности следует увеличить ширину графика, для этого необходимо растянуть окно «График». После изменения параметров отображения график должен выглядеть согласно рисунку (Рисунок 27).

Рисунок 27. Окно графика с измененными параметрами отображения.

На графике отображается последовательность бит закодированного сообщения. До момента времени 7.2 секунды передаются информационные биты, после – проверочные биты. В результате моделирования получена последовательность проверочных бит «010011», что соответствует ожидаемому результату. Модель CRC-кодера работает корректно.

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

Разработка модели источника данных

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

Требуется удалить блоки «Кусочно постоянная» и «Временной график». Для удаления блока следует:
  1. Выделить блок и вызвать контекстное меню блока.
  2. В контекстном меню блока выбрать пункт «Удалить» (Рисунок 28).

    Рисунок 28. Окно проекта с пунктом «Удалить», выбранным в контекстном меню блока.

Необходимо разработать модель источника данных в виде одного блока, для этого требуется добавить на схему блок «Субмодель» из вкладки «Субструктуры», задать ему подпись «Источник» и разместить на схеме согласно рисунку (Рисунок 29).

Рисунок 29. Окно проекта с добавленным блоком «Субмодель».

Следует зайти в субмодель с подписью «Источник», добавить в рабочую область субмодели, разместить и соединить линиями связи, согласно рисунку (Рисунок 30), следующие блоки:
  • 1 блок «Константа» и 1 блок «Меандр» из вкладки «Источники». Данные блоки будут формировать сигналы, необходимые для работы источника.
  • 1 блок «Порт выхода» из вкладки «Субструктуры». Данный блок необходим для передачи данных через порт блока «Субмодель».
  • 1 блок «Ключ управляемый перекидной по входам тип 1» из вкладки «Ключи». Данный блок необходим для формирования требуемой последовательности бит.
  • 1 блок «Цифровая связь – Генератор псевдослучайной битовой последовательности» из подменю «Источники» вкладки «Цифровая связь». Данный блок будет формировать случайное информационное сообщение.

Рисунок 30. Окно проекта с добавленными и соединенными блоками.

Во время ожидания завершения кодирования информационного сообщения источник должен формировать «0» на выходе, поэтому для блока «Константа» следует задать значение свойства «Значение» равным «0».
Необходимо сформировать сигнал, который будет равен «1» в течение передачи информационных бит и равен «0» в течение передачи нулевых бит. Для этого для блока «Меандр» требуется задать:
  • для свойства «Длительность 1-го полупериода, с» формулу «K * T»;
  • для свойства «Значение 1-го полупериода» значение «1»;
  • для свойства «Длительность 2-го полупериода, с» формулу «P * T»;
  • для свойства «Значение 2-го полупериода» значение «0».

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

Разработка модели канала связи с заданной вероятностью ошибки

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

Требуется добавить на схему 1 блок «Субмодель» из вкладки «Субструктуры», задать ему подпись «Канал 1» и разместить на схеме согласно рисунку (Рисунок 31).

Рисунок 31. Окно проекта с добавленным блоком «Субмодель»

Следует зайти в субмодель с подписью «Канал 1», добавить в рабочую область субмодели, разместить и соединить, согласно рисунку (Рисунок 32), следующие блоки:
  • 1 блок «Константа» и 1 блок «Равномерный шум» из вкладки «Источники». Данные блоки будут формировать сигналы, необходимые для функционирования модели канала связи.
  • 1 блок «Порт входа» и 1 блок «Порт выхода» из вкладки «Субструктуры». Данные блоки необходимы для приема и передачи данных через порты блока «Субмодель».
  • 1 блок «Операция МЕНЬШЕ» и 1 блок «XOR» из вкладки «Логические». Данные блоки необходимы для добавления ошибки к передаваемому сообщению.

Рисунок 32. Окно проекта с добавленными и соединенными блоками.

Модель канала связи должна функционировать следующим образом: блок «Равномерный шум» должен формировать случайное число в диапазоне от 0 до 1, в блоке «Константа» должна задаваться вероятность ошибки в канале связи. Если случайное число меньше заданной вероятности, то к информационному биту добавляется ошибка при помощи блока «XOR».

Для реализации описанной выше логики работы для блока «Равномерный шум» необходимо задать значение свойства «Минимальное значение» равным «0», а для блока «Константа» для свойства «Значение» необходимо задать формулу «E_p».

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

Разработка модели канала связи с заданным количеством ошибок

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

Требуется добавить на схему 1 блок «Субмодель» из вкладки «Субструктуры», задать ему подпись «Канал 2» и разместить на схеме согласно рисунку (Рисунок 33).

Рисунок 33. Окно проекта с добавленным блоком «Субмодель».

Следует зайти в субмодель с подписью «Канал 2», добавить в рабочую область субмодели и разместить, согласно рисунку (Рисунок 34), следующие блоки:
  • 1 блок «Генератор единичных импульсов» из вкладки «Источники». Данный блок будет формировать сигнал, необходимые для функционирования модели канала связи.
  • 1 блок «Порт входа» и 1 блок «Порт выхода» из вкладки «Субструктуры». Данные блоки необходимы для приема и передачи данных через порты блока «Субмодель».
  • 1 блок «Язык программирования» из вкладки «Динамические». Данный блок будет реализовывать алгоритм работы канала связи.
  • 1 блок «XOR» из вкладки «Логические». Данный блок необходим для добавления ошибки к передаваемому сообщению.

Рисунок 34. Окно проекта с добавленными блоками.

Необходимо разработать модель функционирования канала связи в виде кода на языке программирования SimInTech. Для этого двойным нажатием левой кнопкой мыши по блоку «Язык программирования» следует открыть окно редактора скрипта блока, задать скрипт согласно рисунку и нажать кнопку «Закрыть и применить» (Рисунок 35).

Рисунок 35. Окно редактора скрипта блока «Язык программирования».

Для блока «Генератор единичных импульсов» для свойства «Период, с» требуется задать формулу «N * T».
  • Модель канала связи функционирует следующим образом: вероятность возникновения ошибки динамически изменяется в процессе передачи сообщения, благодаря этому возможно гарантировать, что для каждого передаваемого сообщения возникнет заданное количество ошибок.
  • Необходимо соединить блоки согласно рисунку (Рисунок 36).

Рисунок 36. Окно проекта с соединенными блоками.

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

Разработка модели декодера

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

Требуется добавить на схему 1 блок «Субмодель» из вкладки «Субструктуры», задать ему подпись «Декодер» и разместить на схеме согласно рисунку (Рисунок 37).

Рисунок 37. Окно проекта с добавленным блоком «Субмодель».

Следует зайти в субмодель с подписью «Декодер», добавить в рабочую область субмодели следующие блоки:
  • 1 блок «Константа», 1 блок «Меандр» и 2 блока «Генератор единичных импульсов» из вкладки «Источники». Данные блоки будут формировать сигналы, необходимые для функционирования декодера.
  • 1 блок «Мультиплексор» и 1 блок «Суммирование элементов вектора» из вкладки «Векторные». Данные блоки необходимы для определения наличия ошибки в принятом сообщении.
  • 1 блок «Порт входа» и 1 блок «Порт выхода» из вкладки «Субструктуры». Данные блоки необходимы для приема и передачи данных через порты блока «Субмодель».
  • 2 блока «Ключ управляемый перекидной по входам тип 1» из вкладки «Ключи». Данные блоки необходимы для коммутации сигналов декодера.
  • 5 блоков «Логические операции» и 1 блок «Оператор НЕ» из вкладки «Логические». Данные блоки необходимы для реализации обратной связи и инвертирования проверочных бит.
  • 6 блоков «Запаздывание на период квантования» из вкладки «Дискретные». Данные блоки необходимы для моделирования сдвиговых регистров.
Требуется разместить блоки на схеме и задать им подписи согласно рисунку (Рисунок 38).

Рисунок 38. Окно проекта с добавленными блоками.

Поскольку кодер инвертирует проверочные биты, для корректного декодирования принятого сообщения необходимо повторно их инвертировать при помощи блока «Оператор НЕ». Блок «Меандр» должен формировать сигнал управления блоком «Ключ управляемый перекидной по входам тип 1», чтобы он передал информационные биты неинвертированными, а проверочные – инвертированными. Для этого для блока «Меандр» требуется задать:
  • для свойства «Длительность 1-го полупериода, с» формулу «K * T»;
  • для свойства «Значение 1-го полупериода» значение «1»;
  • для свойства «Длительность 2-го полупериода, с» формулу «P * T»;
  • для свойства «Значение 2-го полупериода» значение «0».

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

Для всех блоков «Запаздывание на период квантования» для свойства «Период квантования» необходимо задать формулу «T» и активировать пункт «Добавить порт сброса».

Следует сформировать сигнал сброса, который будет равен «1» в момент времени перед началом декодирования нового информационного сообщения. Для блока «Генератор единичных импульсов» с подписью «Управление сбросом» для свойства «Период, с» требуется задать формулу «N * T».

В алгоритме декодирования используются операции «XOR», поэтому для каждого блока «Логические операции» требуется открыть окно свойств, в поле «Значение» свойства «Тип операнда» открыть список доступных операций и выбрать «(ИСКЛЮЧАЮЩЕЕ ИЛИ, XOR)».

Для определения наличия ошибки в полученном сообщении следует просуммировать значения, оставшиеся в сдвиговых регистрах после завершения декодирования, при помощи блока «Суммирование элементов вектора». Необходимо объединить 6 сигналов с каждого регистра в один вектор, поэтому для блока «Мультиплексор» требуется задать значение свойства «Количество портов» равным «6».

Сигнал о наличии ошибки будет сформирован в момент окончания декодирования, во время декодирования необходимо формировать на выходе декодера нулевой сигнал. Для блока «Константа» требуется задать значение свойства «Значение» равным «0».

Для того, чтобы в момент окончания декодирования сигнал о наличии или отсутствии ошибки был подан на выход декодера, необходимо сформировать сигнал управления выходным ключом. Для блока «Генератор единичных импульсов» с подписью «Управление выходом» требуется:
  • для свойства «Период, с» задать формулу «N * T»;
  • раскрыть группу свойств «Управление фазой и частотой» и в поле «Формула» свойства «Фаза (опережение), с» задать формулу «T».
Необходимо соединить блоки согласно рисунку (Рисунок 39).

Рисунок 39. Окно проекта с соединенными блоками.

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

Разработка алгоритма подсчета ошибок

Для проверки корректности работы декодера необходимо сравнить количество сообщений, переданных с ошибками, с количеством ошибок, распознанных декодером. Для этого требуется добавить и разместить на схеме, согласно рисунку (Рисунок 40), следующие блоки:
  • 1 блок «Сумматор» из вкладки «Операторы». Данный блок необходим вычисления количества ошибок, нераспознанных декодером.
  • 1 блок «Субмодель» из вкладки «Субструктуры». В данном блоке будет разработан алгоритм обнаружения ошибок.
  • 1 блок «Временной график» из вкладки «Вывод данных». Данный блок необходим для отображения результатов моделирования.
  • 2 блока «Счетчик» из вкладки «Логические». Данные блоки необходимы для подсчета количества ошибок.

Рисунок 40. Окно проекта с добавленными блоками.

Добавленному блоку «Субмодель» следует задать подпись «Обнаружение ошибок». Необходимо зайти в субмодель, добавить в рабочую область субмодели, расположить и соединить, согласно рисунку (Рисунок 41), следующие блоки:
  • 1 блок «Константа» и 2 блока «Генератор единичных импульсов» из вкладки «Источники».
  • 1 блок «Суммирование элементов вектора» из вкладки «Векторные».
  • 2 блока «Порт входа» и 1 блок «Порт выхода» из вкладки «Субструктуры». Данные блоки необходимы для приема и передачи данных через порты блока «Субмодель».
  • 1 блок «Ключ управляемый нормально разомкнутый тип 1» из вкладки «Ключи».
  • 1 блок «Операция НЕ РАВНО» из вкладки «Логические».
  • 2 блока «Буфер последовательного ввода данных» из вкладки «Обработка сигналов».

Рисунок 41. Окно проекта с добавленными и соединенными блоками.

Блокам «Генератор единичных импульсов» необходимо задать подписи согласно рисунку (Рисунок 42).

Рисунок 42. Окно проекта с заданными подписями блоков.

Для упрощения идентификации входных портов блока «Субмодель» следует изменить имена входных портов. Для этого необходимо:
  • Двойным нажатием левой кнопкой мыши по блоку «Порт входа» открыть окно редактирования порта.
  • В поле «Имена портов субмодели» задать имя порта в соответствии с именем, отображаемым в графическом изображении соответствующего блока «Порт входа» (Рисунок 43).

Рисунок 43. Окно проекта с заданными именами портов субмодели.

Блоки «Буфер последовательного ввода данных» должны объединять принятые биты в вектор сообщения заданной длины. Для этого для каждого блока «Буфер последовательного ввода данных» для свойства «Размер серии» необходимо задать формулу «N».

После окончания принятия сообщения следует очистить буферы и вывести количество отличающихся бит на выходной порт субмодели. Для блока «Генератор единичных импульсов» с подписью «Управление сбросом» для свойства «Период, с» требуется задать формулу «N * T».

Для блока «Генератор единичных импульсов» с подписью «Управление выходом» для свойства «Период, с» требуется задать формулу «N * T» и для свойства «Фаза (опережение), с» задать формулу «T».

Блок «Операция НЕ РАВНО» должен сравнивать между собой элементы двух векторов. Для блока «Операция НЕ РАВНО» для свойства «Тип второго операнда» следует задать значение «Вектор».

Необходимо выйти из рабочей области субмодели и для блока «Сумматор» задать значение свойства «Весовые множители для каждого из входов» равным «[-1, 1]».

Требуется соединить блоки на схеме согласно рисунку (Рисунок 44).

Рисунок 44. Окно проекта с соединенными блоками.

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

Моделирование передачи кодированных данных

Для получения более корректных результатов моделирования следует увеличить количество передаваемых кодовых слов. Требуется открыть скрипт проекта и задать значение глобальной константы «W» равным «10000».

Необходимо провести моделирование передачи данных и изучить зависимость способности CRC-декодера к обнаружению ошибок от вероятности возникновения ошибки. Вероятность ошибки задается в глобальной константе «E_p» в скрипте проекта. Требуется задать вероятность ошибки равной «0.05» и провести моделирование.

После завершения процесса моделирования следует включить отображение значений на линиях связи одинарным нажатием левой кнопкой мыши на кнопку «Показать значения на линиях связи» (Рисунок 45).

Рисунок 45. Окно проекта с выделенной кнопкой «Показать значения на линиях связи».

Количество нераспознанных ошибок будет отображаться на линии связи, подключенной к блоку «Временной график», общее количество ошибок будет отображаться на линии связи, подключенной к порту «+» блока «Сумматор» (Рисунок 46).

Рисунок 46. Окно проекта с активированным режимом «Показать значения на линиях связи».

Вероятность необнаруженной ошибки определяется как отношение количества необнаруженной ошибки к общему количеству ошибок. При значении вероятности битовой ошибки равной «0.05» вероятность необнаруженной ошибки составляет примерно (для данных с рисунка 46):

Требуется задать вероятность ошибки равной «0.15» и провести моделирование. При данном значении вероятности битовой ошибки вероятность необнаруженной ошибки составляет примерно 0.015.

Требуется задать вероятность ошибки равной «0.8» и провести моделирование. При данном значении вероятности битовой ошибки вероятность необнаруженной ошибки составляет примерно 0.016.

В результате увеличения вероятности возникновения ошибки вероятность необнаруженной ошибки увеличивается нелинейно.

Необходимо провести моделирование передачи данных и изучить зависимость способности CRC-декодера к обнаружению ошибок от длины передаваемого сообщения и количества ошибок, возникших при передаче сообщения. Требуется удалить линии связи, подключенные к блоку «Субмодель» с подписью «Канал 1» и затем соединить блоки на схеме согласно рисунку (Рисунок 47).

Рисунок 47. Окно проекта с измененной моделью.

Длина информационной части передаваемого сообщения задается в глобальной константе «K» в скрипте проекта. Требуется задать длину информационной части равной «10», таким образом длина сообщения составит «16» бит. Количество ошибок задается в глобальной переменной «E_n» в скрипте проекта. Требуется задать количество ошибок равным «1» и провести моделирование. При данном сочетании значений параметров количество необнаруженных ошибок равно «0».

Аналогичным образом необходимо провести моделирование для всех сочетаний параметров из таблицы (Таблица 1) и занести в таблицу результаты моделирования (количество необнаруженных ошибок).
Таблица 1. Количество необнаруженных ошибок.

В результате моделирования необнаруженные ошибки должны быть зафиксированы только при количестве ошибок равном «2» и длине сообщения равной «32» и «64». Это связано с тем, что CRC-код позволяет обнаружить любое нечетное количество ошибок в сообщении. Данный результат подтверждает, что способность CRC-декодера к обнаружению ошибок зависит от количества ошибок в сообщении.

Отсутствие необнаруженных ошибок при количестве ошибок равном «2» и длине сообщения равной «16» подтверждает, что способность CRC-декодера к обнаружению ошибок зависит от длины передаваемого сообщения.

Перед завершением выполнения лабораторной работы необходимо сохранить проект.

Самостоятельная разработка модели CRC-кодера

Порядок выполнения лабораторной работы

Необходимо провести исследование работы CRC-кода согласно исходным данным, приведенным в таблице (Таблица 3). В ходе выполнения задания требуется:
  1. Преобразовать полиномиальный генератор g(X) из шестнадцатеричной формы к виду формулы.
  2. Преобразовать в двоичную форму исчисления значения параметров Init, XorOut и Check.
  3. Сформировать схему систематического кодера линейного циклического кода с учетом всех параметров таблицы вариантов задания.
  4. Сформировать схему вычисления синдрома на основе (n - k)-разрядного регистра сдвига.
  5. Провести разработку модели кодера и декодера, провести моделирование и заполнить таблицу (Таблица 2) зависимости вероятности необнаруженных ошибок «Pнеоб» от вероятности битовой ошибки «Ep» в канале связи.
  6. Определить наименьшую длину пакета ошибок, при которой появляются необнаруженные ошибки.
Таблица 2. Вероятность необнаруженных ошибок.
Ep 0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08
Pнеоб                  
Ep 0.09 0.1 0.11 0.12 0.13 0.14 0.15 0.16 0.17
Pнеоб                  
Таблица 3. Варианты задания.
Alg g(X) Init RefIn refOut XorOut Check
1 CRC-8 0x07 0x00 false false 0x00 0xF4
2 CRC-8/CDMA2000 0x9B 0xFF 0x00 0xDA
3 CRC-8/AUTOSAR 0x2F 0xFF 0xFF 0xDF
4 CRC-8/DVB-S2 0xD5 0x00 0x00 0xBC
5 CRC-8/DARC 0x39 0x00 0x00 0x15
6 CRC-8/I-CODE 0x1D 0xFD 0x00 0x7E
7 CRC-8/ITU 0x07 0x00 0x55 0xA1
8 CRC-8/GSM-A 0x1D 0x00 0x00 0x37
9 CRC-8/LTE 0x9B 0x00 0x00 0xEA
10 CRC-8/NRSC-5 0x31 0xFF 0x00 0xF7
Параметры CRC кодов (степень всех полиномов восьмая):
  • Alg – Краткое обозначение алгоритма.
  • g(X) – порождающий полином, представленный шестнадцатеричным числом.
  • Init – исходное содержимое сдвигового регистра на момент запуска вычислений для каждого нового кодового слова.
  • RefIn – логический параметр, который указывает, что биты входного сообщения обращаются, если его значение равно «true».
  • RefOut – логический параметр, который указывает, что содержимое регистров полиномиального генератора обращается, если его значение равно «true».
  • XorOut – 8-битное значение, обозначаемое шестнадцатеричным числом. Оно комбинируется с конечным содержимым регистра (после стадии RefOut), прежде чем будет получено окончательное значение контрольной суммы.
  • Check – контрольное значение, которое может быть использовано для слабой проверки правильности реализации модели в SimInTech.

Контрольные вопросы

  1. Описать типы соединений в системах связи. Что между ними общего и каковы различия?
  2. Что такое процедура автоматического запроса повторной передачи? Какие типы ARQ существуют, описать особенности каждого из них.
  3. Дать определение циклическому коду. Привести пример кодирования информационного сообщения в несистематической форме.
  4. По какой формуле вычисляется полином систематически закодированного сообщения? Привести пример кодирования информационного сообщения в систематической форме.
  5. Что такое двоичный симметричный канал? Изобразить диаграмму переходов. Как определяется вероятность ошибки в таком канале? Какова пропускная способность этого канала?
  6. Что такое двоичный симметричный канал со стираниями, изобразить диаграмму переходов. Как определяется вероятность ошибки в таком канале? Какова пропускная способность этого канала?
  7. Пояснить принцип построения генераторной и проверочной матриц по соответствующим полиномам. Привести примеры.
  8. Описать основные свойства кодов CRC. Как определяется порождающий многочлен для этого класса кодов?

Заключение

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