Коррекция ошибок

Содержание

Введение. 3

1. Обнаружение  ошибок. 4

2. Коррекция  ошибок. 6

3. Циклические  коды. 11

4. Линейные  блочные коды. 15

Заключение 18

Литература. 19

Введение.

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

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

Первое направление носило чисто алгебраический характер и  преимущественно рассматривало  блоковые коды. Первые блоковые коды были введены в 1950 г., когда Хэмминг  описал класс блоковых кодов, исправляющих одиночные ошибки.

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

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

1. Обнаружение ошибок.

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

Простейшим способом обнаружения  ошибок является контроль по четности. Обычно контролируется передача блока  данных (М бит). Этому блоку ставится в соответствие кодовое слово  длиной N бит, причем N>M. Избыточность кода характеризуется величиной 1–M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность).

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

Пусть А и Б две двоичные кодовые последовательности равной длины. Расстояние Хэмминга между двумя этими кодовыми последовательностями равно числу символов, которыми они отличаются. Например, расстояние Хэмминга между кодами 00111 и 10101 равно 2.

Можно показать, что для  детектирования ошибок в n битах, схема  кодирования требует применения кодовых слов с расстоянием Хэмминга не менее N+1. Можно также показать, что для исправления ошибок в N битах необходима схема кодирования  с расстоянием Хэмминга между  кодами не менее 2N+1. Таким образом, конструируя  код, мы пытаемся обеспечить расстояние Хэмминга между возможными кодовыми последовательностями больше, чем оно  может возникнуть из-за ошибок.

Широко распространены коды с одиночным битом четности. В  этих кодах к каждым М бит добавляется 1 бит, значение которого определяется четностью (или нечетностью) суммы  этих М бит. Так, например, для двухбитовых кодов 00, 01, 10, 11 кодами с контролем четности будут 000, 011, 101 и 110. Если в процессе передачи один бит будет передан неверно, четность кода из М+1 бита изменится.

Предположим, что частота  ошибок (BER) равна р=10^-4. В этом случае вероятность передачи 8 бит с ошибкой составит: 1–(1–p)⁸=7,9∙10^-4.

Добавление бита четности позволяет детектировать любую  ошибку в одном из переданных битах. Здесь вероятность ошибки в одном  из 9 бит равна 9p(1–p)⁸. Вероятность же реализации необнаруженной ошибки составит: 1– (1– p)⁹ – 9p(1– p)⁸ = 3,6∙10^-7.

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

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

2. Коррекция ошибок.

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

Но существуют и более  простые методы коррекции ошибок. Например, передача блока данных, содержащего N строк и M столбцов, снабженных битами четности для каждой строки и столбца. Обнаружение ошибки четности в строке i и столбце j указывает на бит, который  должен быть инвертирован. Может показаться, что в случае, когда неверны  два бита, находящиеся в разных строках и столбцах, они также  могут быть исправлены. Но это не так. Ведь нельзя разделить варианты i1,j1 - i2,j2 и i1,j2 - i2,j1. Этот метод может быть развит путем формирования блока данных с N строками, M столбцами и K слоями. Здесь биты четности формируются для всех строк и столбцов каждого из слоев, а также битов, имеющих одинаковые номера строк и столбцов i,j. Полное число битов четности в этом случае равно (N+M+1)×K +(N+1)×(M+1). Если M=N=K=8, число бит данных составит 512, а число бит четности - 217. Нетрудно видеть, что в этом случае число исправляемых ошибок будет больше 1. (Рис. 1).

Рис. 1. Метод коррекции более одной  ошибки в блоке данных

(битам  данных соответствуют окрашенные  квадраты)

Алгоритм Хэмминга.

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

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

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

 Для того, чтобы понять работу данного алгоритма, рассмотрим пример.

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

 На этом этапе стоит  определиться с, так называемой, длиной информационного слова,  то есть длиной строки из  нулей и единиц, которые мы  будем кодировать. Допустим, у нас  длина слова будет равна 16. Таким образом, нам необходимо  разделить наше исходное сообщение  («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:

 и

 После этого процесс  кодирования распараллеливается, и  две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.

 Прежде всего, необходимо  вставить контрольные биты. Они  вставляются в строго определённых  местах — это позиции с номерами, равными степеням двойки. В нашем  случае (при длине информационного  слова в 16 бит) это будут  позиции 1, 2, 4, 8, 16. Соответственно, у  нас получилось 5 контрольных бит  (выделенные):

 Было:

 Стало:

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

Вычисление контрольных  бит.

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

 Здесь знаком «X»  обозначены те биты, которые контролирует  контрольный бит, номер которого  справа. То есть, к примеру, бит  номер 12 контролируется битами  с номерами 4 и 8. Ясно, что чтобы  узнать какими битами контролируется  бит с номером N надо просто  разложить N по степеням двойки.

 Но как же вычислить  значение каждого контрольного  бита? Делается это очень просто: берём каждый контрольный бит  и смотрим, сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль, в противном случае ставим единицу.

Можно конечно и наоборот, если число чётное, то ставим единицу, в противном случае, ставим 0. Главное, чтобы в «кодирующей» и «декодирующей» частях алгоритм был одинаков. (Мы будем  применять первый вариант).

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

 и для второй части: 

Декодирование и  исправление ошибок.

 Теперь, допустим, мы получили  закодированное первой частью  алгоритма сообщение, но оно  пришло к нас с ошибкой. К примеру, мы получили такое (11-ый бит передался неправильно):

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

 Как мы видим, контрольные  биты под номерами: 1, 2, 8 не совпадают  с такими же контрольными битами, которые мы получили. Теперь просто  сложив номера позиций неправильных  контрольных бит (1 + 2 + 8 = 11) мы получаем  позицию ошибочного бита. Теперь  просто инвертировав его и  отбросив контрольные биты, мы  получим исходное сообщение в первозданном виде.

Метод коррекции ошибок FEC.

Для FEC(Forward Error Correction)-кодирования иногда используется метод сверки, который впервые был применен в 1955 году. Главной особенностью этого метода является сильная зависимость кодирования от предыдущих информационных битов и высокие требования к объему памяти. FEC-код обычно просматривает при декодировании 2-8 бит десятки или даже сотни бит.

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

Одним из широко используемых разновидностей коррекции ошибок является турбо кодирование, разработанное  американской аэрокосмической корпорацией. В этой схеме комбинируется два  или более относительно простых  кодов свертки. В FEC, также как  и в других методах коррекции  ошибок (коды Хэмминга, алгоритм Рида-Соломона и др.), блоки данных из k бит снабжаются кодами четности, которые пересылаются вместе с данными, и обеспечивают не только детектирование, но и исправление  ошибок. Каждый дополнительный (избыточный) бит является сложной функцией многих исходных информационных бит. Исходная информация может содержаться в  выходном передаваемом коде, тогда  такой код называется систематическим, а может и не содержаться.

В результате через канал  передается n-битовое кодовое слово (n>k). Конкретная реализация алгоритма FEC характеризуется комбинацией (n,k). Применение FEC в Интернет регламентируется документом RFC-3452. Коды FEC могут исключить необходимость обратной связи при потере или искажении доставленных данных (запросы повторной передачи). Особенно привлекательна технология FEC при работе с мультикастинг-потоками, где ретрансмиссия не предусматривается.

В 1974 году Йозеф Оденвальдер (Joseph Odenwalder) объединил возможности алгебраического кодирования и метода свертки. Хорошего результата можно добиться, введя специальную операцию псевдослучайного перемешивания бит (interleaver).

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

3. Циклические коды.

Обобщением кодов Хэмминга являются циклические коды BCH (Bose-Chadhuri-Hocquenghem). Циклические коды являются частным случаем линейных и представляют собой наиболее разработанную часть последних. Основным их достоинством является простота технической реализации, благодаря чему они и обратили на себя внимание специалистов. Ценным свойством таких кодов является способность обнаруживать не только одиночные ошибки, но и пакеты ошибок. Пакетом ошибок длиной L называют число разрядов сообщения, искаженных подряд.

Свое название циклические  коды получили из-за следующего свойства: если комбинация a_n-1a_n-2 ... a₁a₀ относится к коду, то комбинация, полученная путем циклического сдвига элементов, т.е. комбинация a_n-2 ... a₁a₀a_n-1, также относится к коду. Направление сдвига не имеет значения. Один сдвиг в одном направлении эквивалентен n-1 сдвигам в другом направлении.

 Математической основой  построения циклических кодов  является представление кодовых  комбинаций в виде многочленов  от некоторой переменной x с коэффициентами, равными элементам кодовых комбинаций, и операцией по mod2. Кодовая комбинация 

a_n-1a_n-2 ... a₁a₀

представляется многочленом 

a_n-1x^n-1 + a_n-2x^n-2 + ... + a₁x + a₀

Пример. Многочлен кодовой комбинации 01001 имеет вид x³ + 1.

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

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

Кодовый полином.

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

Свойства циклических  кодов:

• Минимальное кодовое расстояние d циклического кода не превышает числа членов порождающего многочлена.
• Циклический код с порождающим многочленом степени r > 1 обнаруживает любую одиночную и любую двойную ошибку, т.е. имеет d > 3.
• Код с порождающим многочленом x + 1 является кодом с четным числом единиц.
• Циклический код с порождающим многочленом g(x)(x+1) имеет d > 4.
• Код с порождающим многочленом g(x) степени r обнаруживает все пакеты ошибок длины r или меньше.

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

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

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

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

• Контроль циклически избыточным кодом — CRC (Cyclical Redundancy Check). Это гораздо  более  мощный  и  широко  используемый  метод  обнаружения  ошибок передачи  информации.  Он  обеспечивает  обнаружение  ошибок  с  высокой вероятностью.  Кроме  того,  этот  метод  обладает  рядом  других  полезных  моментов, которые могут найти свое воплощение в практических задачах. 

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

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

Redundancy Check. CRC некоторой последовательности вычисляется на основании другой (исходной) битовой последовательности.  Главная  особенность  (и  практическая  значимость)  значения  CRC  состоит  в том,  что  оно  однозначно  идентифицирует  исходную  битовую  последовательность  и  поэтому используется  в  различных  протоколах  связи,  а  также  для  проверки  целостности  блоков  данных, передаваемых различными устройствами. Благодаря относительной простоте алгоритм вычисления CRC часто реализуется на аппаратном уровне.

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

фиксированное  двоичное  число  (полином,  CRC-полином,  генераторный  полином,  англ.  generator polinomial). Интерес представляет остаток от этого деления, который и является значением CRC. Все, что теперь требуется, — это некоторым образом запомнить его и передать вместе с исходной последовательностью. Приемник данной информации всегда может таким же образом выполнить деление  и  сравнить  его  остаток  с  исходным  значением  CRC.  Если они  равны,  то  считается,  что исходное сообщение не повреждено, и т. д. Степенью  CRC-полинома  W  называют  позицию  самого  старшего  единичного  бита.

Например, степенью полинома 10011₂  равна 4. Для вычисления CRC используют специальную т.н. полиномиальную арифметику.

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

4. Линейные блочные коды.

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

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

В системах связи возможны несколько стратегий борьбы с  ошибками:

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

Блоковые коды. Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Тогда соответствующий блоковый код обычно обозначают (n,k) . При этом число R= k/n называется скоростью кода.

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

Пример  линейного блочного кода  (6, 3).

 Код (6, 3) состоит из 2^k = 2³ = 8 векторов сообщений, т.е. восьми кодовых слов. В векторном пространстве V₆  имеется 2ⁿ = 2⁶ = 64  6-кортежей. Восемь кодовых слов, показанных в таблице 1, образуют в V₆ подпространство (имеется нулевой вектор, сумма любых двух кодовых слов дает кодовое слово этого же подпространства). Таким образом, эти кодовые слова представляют линейный блочный код. Возникает вопрос о соответствии кодовых слов и сообщений для этого кода (6, 3). Однозначного соответствия для отдельных кодов (n, k) не существует.

Таблица 1. Соответствие кодовых слов и сообщений

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

Так как множество  кодовых слов, составляющих линейный блочный код, является k–мерным подпространством n–мерного двоичного векторного пространства, то всегда можно найти такое множество п–кортежей (с числом элементов, меньшим 2^k), которое может генерировать все 2^k кодовых слова подпространства. Генерирующее множество векторов охватывает все подпространство. Наименьшее линейно независимое множество, охватывающее подпространство, называется базисом подпространства, а число векторов в этом базисном множестве называется размерностью подпространства. Пусть V₁, V₂, ..., V_k любое базисное множество k линейно независимых п–кортежей. Тогда это базисное множество можно использовать для генерации нужных векторов линейного блочного кода, поскольку каждый вектор кода является линейной комбинацией V₁, V₂, ..., V_k.  Другими словами, каждое из множества 2^k кодовых слов U можно представить следующим образом:

U = m₁ V₁ + т₂ V₂ + ... + т_k V_k ,                                        (1)

где т_i – это цифры сообщения 0 или 1, а i = 1, ... , k.

Кодирование линейного блочного (n, k) – кода задается порождающей матрицей G_n,k, которая определяется как массив размером k п [2, 3]:

G_n,k = .                                    (2)

Кодовые векторы  представляются векторами-строками, таким  образом, последовательность k бит сообщения, т.е. сообщение m, представляется как вектор-строка: т = т₁, т₂, ... , т_k.