Введение
Семейство кодов коррекции ошибок, кодирующих данные блоками.
В теории кодирования, блочные коды представляют собой большое и важное семейство кодов коррекции ошибок, кодирующих данные блоками. Существует огромное количество примеров блочных кодов, многие из которых имеют широкий спектр практических применений. Абстрактное определение блочных кодов концептуально полезно, поскольку оно позволяет теоретикам кодирования, математикам и специалистам в области компьютерных наук изучать ограничения всех блочных кодов в едином ключе. Эти ограничения часто принимают форму границ, связывающих различные параметры блочного кода, такие как его скорость и способность обнаруживать и исправлять ошибки. Примерами блочных кодов являются коды Рида — Соломона, коды Хэмминга, коды Адамара, коды Экспандера, коды Голея и коды Рида — Мюллера. Эти примеры также относятся к классу линейных кодов и поэтому называются линейными блочными кодами. В частности, эти коды известны как алгебраические блочные коды или циклические блочные коды, поскольку они могут быть сгенерированы с использованием булевых многочленов. Алгебраические блочные коды обычно аппаратно декодируются с помощью алгебраических декодеров. Термин «блочный код» также может относиться к любому коду коррекции ошибок, который обрабатывает блок входных битов данных для получения блока выходных битов данных. Следовательно, блочный кодер является устройством без памяти. В соответствии с этим определением коды, такие как турбо-коды, завершенные свёрточные коды и другие итеративно декодируемые коды (подобные турбо-кодам), также будут считаться блочными кодами. Не завершенный свёрточный кодировщик является примером неблочного (нефреймового) кода, который имеет память и вместо этого классифицируется как древесный код. В данной статье рассматриваются «алгебраические блочные коды».
In coding theory, block codes are a large and important family of error correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors. Examples of block codes are Reed–Solomon codes, Hamming codes, Hadamard codes, Expander codes, Golay codes, and Reed–Muller codes. These examples also belong to the class of linear codes, and hence they are called linear block codes. More particularly, these codes are known as algebraic block codes, or cyclic block codes, because they can be generated using boolean polynomials. Algebraic block codes are typically hard decoded using algebraic decoders. The term block code may also refer to any error correcting code that acts on a block of bits of input data to produce bits of output data Consequently, the block coder is a memoryless device. Under this definition codes such as turbo codes, terminated convolutional codes and other iteratively decodable codes (turbo like codes) would also be considered block codes. A non terminated convolutional encoder would be an example of a non block (unframed) code, which has memory and is instead classified as a tree code. This article deals with "algebraic block codes".
Алфавит Σ
Поток данных, подлежащий кодированию, моделируется как строка над некоторым алфавитом. Размер алфавита часто обозначается как q. Если q = 2, то блочный код называется двоичным блочным кодом. Во многих приложениях полезно рассматривать q как степень простого числа и отождествлять его с конечным полем GF(q).
Длина сообщения k
Сообщения являются элементами , то есть последовательностями длины. Следовательно, число называется длиной сообщения или размерностью блочного кода.
Длина блока n
Длина блока блокового кода — это число символов в блоке. Следовательно, элементы являются строками длины *n* и соответствуют блокам, которые может получить приёмник. Поэтому их также называют принятыми словами. Если *x* кодирует некоторое сообщение *m*, то *x* называется кодовым словом для *m*.
Популярная нотация
В обозначении описывается блочный код над алфавитом размера , с длиной блока , длиной сообщения и расстоянием . Если блочный код является линейным, то квадратные скобки в обозначении используются для указания этого факта. Для двоичных кодов с , индекс иногда опускается. Для кодов с максимальным разделением расстояние всегда равно , но иногда точное расстояние неизвестно, сложно доказать или указать, либо не требуется. В таких случаях компонент может быть пропущен. Иногда, особенно для некодовых блоков, обозначение используется для кодов, содержащих кодовых слов длины . Для блочных кодов с сообщениями длины над алфавитом размера , это число будет .
Примеры
Как упоминалось выше, существует огромное количество кодов коррекции ошибок, которые на самом деле являются блочными кодами. Первым кодом для исправления ошибок был код Хамминга (7,4), разработанный Ричардом В. Хаммингом в 1950 году. Этот код преобразует сообщение, состоящее из 4 бит, в кодовое слово из 7 бит, добавляя 3 бита четности. Следовательно, этот код является блочным кодом. Оказывается, что это также линейный код и что у него расстояние 3. В вышеуказанной сокращенной записи это означает, что код Хамминга (7,4) является [7,4]-кодом. Коды Рида — Соломона — это семейство кодов с n и k, где k является степенью простого числа. Коды ранга — это семейство кодов с. Коды Хадамара — это семейство кодов с n и k.
Собственности обнаружения и исправления ошибок
Кодовое слово можно рассматривать как точку в пространстве размерности, а код является подмножеством. Код с расстоянием *d* означает, что для любого кодового слова *x*, не существует другого кодового слова в шаре Хамминга с центром в *x* и радиусом *d*, который определяется как множество слов размерности, расстояние Хамминга до которых не превышает *d*. Аналогично, код с (минимальным) расстоянием *d* обладает следующими свойствами:
can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius , no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of , the errors are detected (but no guarantee to correct). can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius , the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word , as long as the number of errors is no more than , there is only one codeword in the hamming ball centered at with radius , therefore all errors could be corrected. In order to decode in the presence of more than errors, list decoding or maximum likelihood decoding can be used. can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.
* может обнаруживать *d-1* ошибок: поскольку кодовое слово *x* является единственным кодовым словом в шаре Хамминга с центром в нем и радиусом *d-1*, ни один шаблон ошибок, содержащий *d-1* или меньше ошибок, не может изменить одно кодовое слово на другое. Когда приемник обнаруживает, что полученный вектор не является кодовым словом кода, ошибки обнаруживаются (но нет гарантии исправления).
can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius , no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of , the errors are detected (but no guarantee to correct). can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius , the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word , as long as the number of errors is no more than , there is only one codeword in the hamming ball centered at with radius , therefore all errors could be corrected. In order to decode in the presence of more than errors, list decoding or maximum likelihood decoding can be used. can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.
* может исправлять *⌊(d-1)/2⌋* ошибок. Поскольку кодовое слово *x* является единственным кодовым словом в шаре Хамминга с центром в нем и радиусом *⌊(d-1)/2⌋*, два шара Хамминга с центрами в двух различных кодовых словах и радиусом *⌊(d-1)/2⌋* не перекрываются друг с другом. Поэтому, если рассматривать коррекцию ошибок как нахождение кодового слова, ближайшего к полученному слову *y*, то, пока количество ошибок не превышает *⌊(d-1)/2⌋*, в шаре с радиусом *⌊(d-1)/2⌋* и центром в *y* находится только одно кодовое слово, следовательно, все ошибки могут быть исправлены. Для декодирования при наличии более чем *⌊(d-1)/2⌋* ошибок можно использовать декодирование по списку или декодирование с максимальным правдоподобием.
can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius , no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of , the errors are detected (but no guarantee to correct). can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius , the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word , as long as the number of errors is no more than , there is only one codeword in the hamming ball centered at with radius , therefore all errors could be corrected. In order to decode in the presence of more than errors, list decoding or maximum likelihood decoding can be used. can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.
* может исправлять *d/2* стираний. Под стиранием подразумевается, что позиция стертого символа известна. Корректировка может быть достигнута с помощью *проходного* декодирования: при проходном декодировании стертая позиция заполняется символом и выполняется коррекция ошибок. Должен существовать хотя бы один проход, при котором количество ошибок не превышает *⌊(d-1)/2⌋*, и, следовательно, стирания могут быть исправлены.
can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius , no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of , the errors are detected (but no guarantee to correct). can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius , the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word , as long as the number of errors is no more than , there is only one codeword in the hamming ball centered at with radius , therefore all errors could be corrected. In order to decode in the presence of more than errors, list decoding or maximum likelihood decoding can be used. can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.