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

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

           Третий классификационный признак  относится только к блочным  разделимым кодам – они подразделяются на систематические (линейные) и несистематические.

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

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

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

 

 

    1.7 Применение помехоустойчивых  кодов в системах железнодорожной  автоматики, телемеханики и связи.

 

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

        В  агрегатной системе диспетчерской  централизации (АСДЦ) для обнаружения ошибок используются систематические помехоустойчивые коды: код Бауэра, являющийся разновидностью кода с простым повторением, и код с одной проверкой на нечетность (проверкой по паритету). Принцип кодирования кодом Бауэра состоит в повторении информационной последовательности из к символов, если она содержит нечетное число единиц, и инверсном повторении информационных символов — при четном числе единиц. Например, информационным последовательностям 0111 и 0101 соответствуют кодовые комбинации U_{ = 01110111 и U₂ = 0I011010. Очевидно, что избыточность кода Бауэра равна 0,5.

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

В применяемых на железнодорожном  транспорте цифровых системах связи и передачи данных наибольшее распространение получили циклические коды для обнаружения ошибок различной кратности, называемые кодами циклической проверки избыточности (CRC — Cyclic Redundancy Check), а в сотовых системах связи с подвижными объектами также и сверточные коды для исправления независимых ошибок в сочетании с устройствами перемежения. Например, в модемных протоколах коррекции ошибок и протоколах каналов передачи кадров в сетях передачи данных используется код CRC с производящим многочленом g(x) = х¹⁶ + х¹² + х⁵ + 1. Код CRC-16 содержит 16 проверочных символов, имеет минимальное кодовое расстояние d_min = 4 и позволяет обнаруживать ошибки до третьей кратности включительно.

      Так код CRC-16 позволяет обнаружить 99,9985 % ошибок. Наряду с ним в модемных протоколах V42 используется код CRC с производящим многочленом g(x) = х³² + х²⁶ + х²³ + х²² + х¹⁶ + х¹² + х¹¹ + х^ш + + х⁸ + х⁷ + х⁵ + х⁴ + х² + х + 1 и d_min = 15.

 

В сетях высокоскоростной передачи данных (ATM сетях) используются укороченные циклические коды БЧХ (Боуза—Чоудхури—Хо-квингема). Например, для обнаружения ошибок до третьей кратности и исправления ошибок первой кратности в заголовках ячеек ATM используется код CRC с производящим многочленом g(x) = х⁸ + х²+ х+1 . Для обнаружения однократных и двукратных ошибок в протокольных блоках данных ATM сетях используется CRC код с производящим

многочленом g(x) = х⁴ + х + I и d_min = 3.

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

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

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

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

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

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

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

 

 

           2 Постановка задачи.

 Выбрать  систему кодирования и на основе  выбранного метода разрaботать ИС Построить систематический код для передачи 31 разрядной кодовой комбинации с исправлением однократной ошибки.

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

 

 

2.1 Построение систематических кодов  и их свойства

 

Рассмотрим (n,k) код. Кодовую комбинацию представим в виде кодового вектора, у которого информационные биты обозначим u₁ … u_k, а проверочные – p₁… p_r: U = {u₁, u₂, …, u_k, p₁, p₂,…, p_r}. Поскольку кодирование двоичное, ясно, что каждый бит кода может принимать значение 0 или 1.

(n,k) код называется систематическим (или линейным), если значения всех проверочных бит (p_j) определяются линейными комбинациями информационных бит (u_i), т.е.

Суммирование  в выражении (2.6) осуществляется по модулю 2; коэффициенты в линейных комбинациях c_j,i могут принимать значения 1 или 0 – именно ими определяются свойства кода. В систематических кодах информационные и проверочные биты занимают строго определенные позиции в кодовых комбинациях (но не обязательно, как в приведенном выше случае, сначала одни, затем другие - возможны иные правила относительного расположения частей кодовых комбинаций).

Из 2^k разрешенных кодовых комбинаций (кодовых векторов) всегда можно выделить k линейно независимых:

кодовые векторы U⁽¹⁾ … U^(k) называются линейно независимыми, если выполняется условие α₁U⁽¹⁾ α ₂U⁽²⁾ … α _kU^(k) # 0

при любых наборах значений α _i (α _i = 0 или 1, но не все одновременно 0).

Например, кодовые комбинации U⁽¹⁾ = {1111}; U⁽²⁾ = {1100}; U⁽³⁾ = {1010}; U⁽⁴⁾ = {1001} не являются линейно независимыми, поскольку при α_i = 1 сумма 1·U⁽¹⁾ 1·U⁽²⁾ 1·U⁽³⁾ 1·U⁽⁴⁾ = 0. Напротив, векторы U⁽²⁾, U⁽³⁾ и U⁽⁴⁾ оказываются линейно независимыми, в чем можно убедиться, перебрав различные комбинации коэффициентов α_i.

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

 

Все остальные разрешенные комбинации (небазисные) могут быть получены как  линейные комбинации базисных (включая «нулевую» комбинацию – у нее все α_j,i = 0):

(суммирование  производится по mod 2).

       В производящей матрице можно  выделить информационную подматрицу  размером k × k (будем обозначать ее A_k,k) и проверочную подматрицу размером r × k (будем обозначать ее P_r,k); т.е. производящую матрицу можно представлять как объединение информационной и проверочной подматриц:

G_n,k = A_k,k + P_r,k.

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

        Рассмотрим пример построения  систематического кода с четырьмя  информационными битами, обеспечивающий исправление однократных ошибок. Поскольку k = 4, согласно (2.5) и таблицы из примера 2.4., необходимое число проверочных бит в этом случае r = 3, следовательно, речь идет о построении систематического кода (7,4).

       Однозначность построения подматрицы A_4,4 отсутствует – обязательным является лишь то условие, что все входящие в нее комбинации (т.е. ее строки) должны быть линейно независимы. По этой причине выберем довольно очевидный вариант:

         При построении проверочной подматрицы  мы должны исходить из следующих  положений:

размер  подматрицы – 4 строки и 3 столбца;

поскольку код должен исправлять все однократные  ошибки то, d_min = 3, т.е. вес любой базовой кодовой комбинации должен быть не менее 3 (каждый код должен содержать не менее 3-х единичных бит);