простейший код исправляющий ошибки представляет собой

Корректирующие коды «на пальцах»

3bddaa3d671b4a4c97ca9f731febd6a5Корректирующие (или помехоустойчивые) коды — это коды, которые могут обнаружить и, если повезёт, исправить ошибки, возникшие при передаче данных. Даже если вы ничего не слышали о них, то наверняка встречали аббревиатуру CRC в списке файлов в ZIP-архиве или даже надпись ECC на планке памяти. А кто-то, может быть, задумывался, как так получается, что если поцарапать DVD-диск, то данные всё равно считываются без ошибок. Конечно, если царапина не в сантиметр толщиной и не разрезала диск пополам.

Как нетрудно догадаться, ко всему этому причастны корректирующие коды. Собственно, ECC так и расшифровывается — «error-correcting code», то есть «код, исправляющий ошибки». А CRC — это один из алгоритмов, обнаруживающих ошибки в данных. Исправить он их не может, но часто это и не требуется.

Давайте же разберёмся, что это такое.

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

Внимание! Много текста и мало картинок. Я постарался всё объяснить, но без карандаша и бумаги текст может показаться немного запутанным.

Каналы с ошибкой

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

Ошибка — это маловероятное событие (а иначе зачем нам такой канал вообще, где одни ошибки?), а значит, вероятность двух ошибок меньше, а трёх уже совсем мала. Мы можем выбрать для себя некоторую приемлемую величину вероятности, очертив границу «это уж точно невозможно». Это позволит нам сказать, что в канале возможно не более, чем 8394523d1f4bab66a8544cd365388d87ошибок. Это будет характеристикой канала связи.

Для простоты введём следующие обозначения. Пусть данные, которые мы хотим передавать, — это двоичные последовательности фиксированной длины. Чтобы не запутаться в нулях и единицах, будем иногда обозначать их заглавными латинскими буквами (3ce765dddc59fdb7834b8831b784f9d9, 9e8a3feeef98454766ed27af3effec45, dafe837b2eb473c8c3a2240b85e4ca80, …). Что именно передавать, в общем-то неважно, просто с буквами в первое время будет проще работать.

Кодирование и декодирование будем обозначать прямой стрелкой (aa5f89e80b38f8a0a88dc87d92844440), а передачу по каналу связи — волнистой стрелкой (42c2f022ffd7baa6d576432644678d47). Ошибки при передаче будем подчёркивать.

Например, пусть мы хотим передавать только сообщения b21044c7ee5623f39fb56b8e9e37cb65и 975fa56436c5f1690ce87840c8e4cab7. В простейшем случае их можно закодировать нулём и единицей (сюрприз!):

cd0b654eefd38221121db862132e8710

Передача по каналу, в котором возникла ошибка будет записана так:

cb97d5165f11a19c6eae75c419aebe5c

Цепочки нулей и единиц, которыми мы кодируем буквы, будем называть кодовыми словами. В данном простом случае кодовые слова — это 0fc031d0014dcf57b36106bd16b8e71bи 072cebbbc068c9c66ce5e423466d257c.

Код с утроением

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

140598a30dcf4ab11898490422e2b214

Правда, это нам не очень поможет. В самом деле, рассмотрим канал с одной возможной ошибкой:

dce4df85543d873e4af5208699ba46a0

Какие выводы мы можем сделать, когда получили 6f4321ca5fd6387c5ead448d47576138? Понятно, что раз у нас не две одинаковые цифры, то была ошибка, но вот в каком разряде? Может, в первом, и была передана буква 9e8a3feeef98454766ed27af3effec45. А может, во втором, и была передана 3ce765dddc59fdb7834b8831b784f9d9.

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

8e15207060f1d61f245b45dac479ba73

7d7f5522096fd29b1a46a2e109105217

Получили 345773407bc6097bb36a75fd77042997. Тут у нас есть две возможности: либо это 9e8a3feeef98454766ed27af3effec45и было две ошибки (в крайних цифрах), либо это 3ce765dddc59fdb7834b8831b784f9d9и была одна ошибка. Вообще, вероятность одной ошибки выше вероятности двух ошибок, так что самым правдоподобным будет предположение о том, что передавалась именно буква 3ce765dddc59fdb7834b8831b784f9d9. Хотя правдоподобное — не значит истинное, поэтому рядом и стоит вопросительный знак.

Если в канале связи возможна максимум одна ошибка, то первое предположение о двух ошибках становится невозможным и остаётся только один вариант — передавалась буква 3ce765dddc59fdb7834b8831b784f9d9.

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

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

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

Расстояния между кодами

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

Читайте также:  код тн вэд 8301100000

И вообще, почему этот код работает? Почему нужно именно утраивать для устранения одной ошибки? Наверняка это всё неспроста.

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

Пусть мы передавали 9b83bcabefca1405d3d9a13def283967, а получили 7b76ba2d92cc09b75fa2dc93281e16d4. Видно, что эта цепочка больше похожа на исходные 9b83bcabefca1405d3d9a13def283967, чем на 0704b1ed15106d1d2b79899ae5e6612f. А так как других кодовых слов у нас нет, то и выбор очевиден.

Но что значит «больше похоже»? А всё просто! Чем больше символов у двух цепочек совпадает, тем больше их схожесть. Если почти все символы отличаются, то цепочки «далеки» друг от друга.

Можно ввести некоторую величину dcbb6bd7e62c827340b33ab17902049f, равную количеству различающихся цифр в соответствующих разрядах цепочек 8bbe730e90adaf07435b47deee6a1b38и f3905b5cfab08d98b2d380d5ea75c66c. Эту величину называют расстоянием Хэмминга. Чем больше это расстояние, тем меньше похожи две цепочки.

Например, c29f8fe84dfb241d890cb1e8917f3450, так как все цифры в соответствующих позициях равны, а вот f084ad0259cf5ae870ac7c7f0e0d05c6.

Расстояние Хэмминга называют расстоянием неспроста. Ведь в самом деле, что такое расстояние? Это какая-то характеристика, указывающая на близость двух точек, и для которой верны утверждения:

Достаточно разумные требования.

Математически это можно записать так (нам это не пригодится, просто ради интереса посмотрим):

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

Окрестности

Таким образом, разные цепочки мы считаем точками в каком-то воображаемом пространстве, и теперь мы умеем находить расстояния между ними. Правда, если попытаться сколько нибудь длинные цепочки расставить на листе бумаги так, чтобы расстояния Хэмминга совпадали с расстояниями на плоскости, мы можем потерпеть неудачу. Но не нужно переживать. Всё же это особое пространство со своими законами. А слова вроде «расстояния» лишь помогают нам рассуждать.

Пойдём дальше. Раз мы заговорили о расстоянии, то можно ввести такое понятие как окрестность. Как известно, окрестность какой-то точки — это шар определённого радиуса с центром в ней. Шар? Какие ещё шары! Мы же о кодах говорим.

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

Так, скажем, окрестность кодового слова 9b83bcabefca1405d3d9a13def283967радиуса 1 — это все коды, находящиеся на расстоянии не больше, чем 1 от него, то есть отличающиеся не больше, чем в одном разряде. То есть это коды:

2d759709844a51d6dc838f5d13dcaef9

Да, вот так странно выглядят шары в пространстве кодов.

А теперь посмотрите. Это же все возможные коды, которые мы получим в канале в одной ошибкой, если отправим 9b83bcabefca1405d3d9a13def283967! Это следует прямо из определения окрестности. Ведь каждая ошибка заставляет цепочку измениться только в одном разряде, а значит удаляет её на расстояние 1 от исходного сообщения.

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

Тогда всю нашу систему декодирования можно построить так. Мы получаем какую-то цепочку нулей и единиц (точку в нашей новой терминологии) и смотрим, в окрестность какого кодового слова она попадает.

Сколько ошибок может исправить код?

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

В коде с удвоением между кодовыми словами 25c46037ced90068eb3cf52d71066d17и e271e32cf9e7a71c8768fb8897347417расстояние равно 2 (оба разряда различаются). А значит, если мы построим вокруг них шары радиуса 1, то они будут касаться. Это значит, точка касания будет принадлежать обоим шарам и непонятно будет, к какому из них её отнести.

image loader

Именно это мы и получали. Мы видели, что есть ошибка, но не могли её исправить.

Что интересно, точек касания в нашем странном пространстве у шаров две — это коды 6f4321ca5fd6387c5ead448d47576138и 9ce961470980434e252bc2935d433358. Расстояния от них до центров равны единице. Конечно же, в обычно геометрии такое невозможно, поэтому рисунки — это просто условность для более удобного рассуждения.

В случае кода с утроением, между шарами будет зазор.

image loader

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

В общем случае получаем следующее.

ea7d454ec3534c96b778921baaaf1a78

Этот очевидный результат на самом деле очень важен. Он означает, что код с минимальным кодовым расстоянием ed9a45bf31af169a2a51bbc0f8b09bacбудет успешно работать в канале с 8394523d1f4bab66a8544cd365388d87ошибками, если выполняется соотношение

44dfa8b976be59c14c9a6a5d7d3e8190

Полученное равенство позволяет легко определить, сколько ошибок будет исправлять тот или иной код. А сколько код ошибок может обнаружить? Рассуждения такие же. Код обнаруживает 8394523d1f4bab66a8544cd365388d87ошибок, если в результате не получится другое кодовое слово. То есть, кодовые слова не должны находиться в окрестностях радиуса 8394523d1f4bab66a8544cd365388d87других кодовых слов. Математически это записывается так:

Читайте также:  проверка комплектации авто по вин коду

62e46e92f193d658e261394cf25fd1af

Рассмотрим пример. Пусть мы кодируем 4 буквы следующим образом.

c7440637325918cfbd4b5866b18caff8

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

A B C D
A 3 3 4
B 3 4 3
C 3 4 3
D 4 3 3

Минимальное расстояние 7fc7859f0b9f4b22b16d6ea52b83a2ff, а значит 3f8ac75b6a879e19c78db0861fa69f97, откуда получаем, что такой код может исправить до 1f346d9b27100117fb86975cac12f171ошибок. Обнаруживает же он две ошибки.

0825753aef8ac3320ccc42426cc28f8e

Чтобы декодировать полученное сообщение, посмотрим, к какому символу оно ближе всего.

990e058deb3beb6ccf8177024127ae8b

Минимальное расстояние получилось для символа 3ce765dddc59fdb7834b8831b784f9d9, значит вероятнее всего передавался именно он:

67948987ac5b8f690bb4d5b91c727314

Итак, этот код исправляет одну ошибку, как и код с утроением. Но он более эффективен, так как в отличие от кода с утроением здесь кодируется уже 4 символа.

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

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

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

Интерлюдия: поле GF(2)

Для изложения дальнейшего материала нам потребуются матрицы. А при умножении матриц, как известно мы складываем и перемножаем числа. И тут есть проблема. Если с умножением всё более-менее хорошо, то как быть со сложением? Из-за того, что мы работаем только с одиночными двоичными цифрами, непонятно, как сложить 1 и 1, чтобы снова получилась одна двоичная цифра. Значит вместо классического сложения нужно использовать какое-то другое.

Введём операцию сложения как сложение по модулю 2 (хорошо известный программистам XOR):

e7d44d6564e9b0cf2633a36b2db401d2

Умножение будем выполнять как обычно. Эти операции на самом деле введены не абы как, а чтобы получилась система, которая в математике называется полем. Поле — это просто множество (в нашем случае из 0 и 1), на котором так определены сложение и умножение, чтобы основные алгебраические законы сохранялись. Например, чтобы основные идеи, касающиеся матриц и систем уравнений по-прежнему были верны. А вычитание и деление мы можем ввести как обратные операции.

Множество из двух элементов 2c05055ffdc793bb34b634790fc868e4с операциями, введёнными так, как мы это сделали, называется полем Галуа GF(2). GF — это Galois field, а 2 — количество элементов.

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

b94a25acb893a96976e651ef202ea0df

Это свойство прямо следует из определения.

4accac492ac76a37d4e7c149933cb6ed

А в этом можно убедиться, прибавив 1e6829a256c8a2712f849dc1d2343b62к обеим частям равенства. Это свойство, в частности означает, что мы можем переносить в уравнении слагаемые в другую сторону без смены знака.

Проверяем корректность

Вернёмся к коду с утроением.

8e15207060f1d61f245b45dac479ba73

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

Пусть мы приняли вектор-строку baadee9444d136cdabc2792cdd7d0b6bиз трёх цифр. (Стрелочки над векторами рисовать не будем, так как у нас почти всё — это вектора или матрицы.)

7dea2eec80fbf7be54f729dbdcb723f8

Математически равенство всех трёх цифр можно записать как систему:

dcbfa14db36f88b6d0b323e953feb0df

Или, если воспользоваться свойствами сложения в GF(2), получаем

f3091b3b6b67fd59e45a8fc0803a8bdd

c50df44e2f9f5859cba43f8d5663ac21

В матричном виде эта система будет иметь вид

b69a19eda38cf4b60fa66d8ab8e3b62c

955fd0e010ab92258eac4c0d373027e8

Транспонирование здесь нужно потому, что baadee9444d136cdabc2792cdd7d0b6b— это вектор-строка, а не вектор-столбец. Иначе мы не могли бы умножать его справа на матрицу.

Будем называть матрицу 7d7c03ca917c30cbaff32f62468b0f6fпроверочной матрицей. Если полученное сообщение — это корректное кодовое слово (то есть, ошибки при передаче не было), то произведение проверочной матрицы на это сообщение будет равно нулевому вектору.

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

Кодирование

Итак, у нас есть система для проверки

f3091b3b6b67fd59e45a8fc0803a8bdd

Её решения — это кодовые слова. Собственно, мы систему и строили на основе кодовых слов. Попробуем теперь решить обратную задачу. По системе (или, что то же самое, по матрице 7d7c03ca917c30cbaff32f62468b0f6f) найдём кодовые слова.

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

f0f3af9d3e5c5c4000cdd5f68c7dfd71

Соответствующая система имеет вид:

268d3b578f8d058a74600966f971e802

Чтобы найти кодовые слова соответствующего кода нужно её решить.

В силу линейности сумма двух решений системы тоже будет решением системы. Это легко доказать. Если 366a4b5c5bdf260210b49a89f904efb9и 5d2218e7292f24a1ff72a7ba614d11e9— решения системы, то для их суммы верно

fdb66cfa608c5a9015cad27c3440d76c

что означает, что она тоже — решение.

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

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

Если бы нам не так повезло с системой, то нужно было бы складывая уравнения между собой получить такую систему, чтобы какие-то три переменные встречались по одному разу. Ну, или воспользоваться методом Гаусса. Для GF(2) он тоже работает.

c9ad8bfa78b9a68e428c2ee4524ff003

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

f26b2bc9a9ab9a6d14d51a378653c01f

Всевозможные суммы этих независимых решений (а именно они и будут кодовыми векторами) можно получить так:

4decafd26623b55fecc3e410989a2f5d

где e5ff599baff6f0645acd8a21c6ec8d84равны либо нулю или единице. Так как таких коэффициентов два, то всего возможно bdf1f66d78fc7e311d1aedc2d7a778cdсочетания.

Но посмотрите! Формула, которую мы только что получили — это же снова умножение матрицы на вектор.

b52e4f5de8e6a4b0d62c7b8136d9fe7d

Строчки здесь — линейно независимые решения, которые мы получили. Матрица 5891c82c470a676769aeb056c95b6a3dназывается порождающей. Теперь вместо того, чтобы сами составлять таблицу кодирования, мы можем получать кодовые слова простым умножением на матрицу:

e09c8aafd3a6e3c2e042de8eefc79f3c

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

01360bced5e37deaaac3007e7d6e6b77

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

c65e4a4da6a38487d63d74f66f7bf647

А раз в результате не нулевой вектор, значит код заподозрил неладное. Провести его не удалось. Ура, код работает!

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

224a230c55a1621563cda61f86d4e5a4

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

Ошибка по синдрому

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

Для начала введём такое понятие, как вектор ошибки. Это вектор, на который отличается принятое сообщение от кодового слова. Пусть мы получили сообщение baadee9444d136cdabc2792cdd7d0b6b, а было отправлено кодовое слово c32fda44ca18e68b6bedfbf53e221e57. Тогда вектор ошибки по определению

9bfb66680778c91d712cdf4a98ac64d1

Но в странном мире GF(2), где сложение и вычитание одинаковы, будут верны и соотношения:

45ac591fd86cc1ae3fe37074d535d146

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

Как мы уже говорили раньше, если мы получили сообщение baadee9444d136cdabc2792cdd7d0b6bс ошибкой, то 4b0dd07a61d5d37649e23afda9df7cac. Но ведь векторов, не равных нулю много! Быть может то, какой именно ненулевой вектор мы получили, подскажет нам характер ошибки?

Назовём результат умножения на проверочную матрицу синдромом:

fe7ddd6fbad5d10563908371f1d19ced

И заметим следующее

61c684f19c0be196a0fa7f17bda5aa07

Это означает, что для ошибки синдром будет таким же, как и для полученного сообщения.

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

А очень просто! Помните, мы говорили, что у нескольких ошибок вероятность ниже, чем у одной ошибки? Руководствуясь этим соображением, наиболее правдоподобным будет считать вектором ошибки тот вектор, у которого меньше всего единиц. Будем называть его лидером.

Давайте посмотрим, какие синдромы дают всевозможные 5-элементные векторы. Сразу сгруппируем их и подчеркнём лидеров — векторы с наименьшим числом единиц.

b12933f98d519da099aebf289c08e974 baadee9444d136cdabc2792cdd7d0b6b
9b83bcabefca1405d3d9a13def283967 66f0a897e522557bac0da4ab94f7f88a
7b76ba2d92cc09b75fa2dc93281e16d4 fa3346414ba60ca804b93676cc45b97c
345773407bc6097bb36a75fd77042997 f84650bdb036c1727b1648422c174e75
af59e99d2a84a95ded1d5d6bc44dda2a db4ae18d2d49c3cea79140877800d30e
fd73c958b5ade9f8f6e1fa5738fe196a 7ea11a7cfc5e9f7dc4be76ca871cc7c3
98f0a4197351dfd2f3e8929b2221ab2c 5a45f924fece2ec5505c3330705af94d
938442154c3ae8291ee9d4a9b47dd8fd 4e3319f655a7f4ca84c51ed7a9648aa5
0704b1ed15106d1d2b79899ae5e6612f ff6e1aab514c55c099116bb92fd297fd

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

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

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

83fff15a80b98bdb889c7cc3e1e51f60

Вектор ошибки равен 2ef565c0ef85aad232400f688f7dc46c, а значит ошибка в третьем разряде. Как мы и загадали.

Что же дальше?

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

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

Если вас заинтересовали подробности, то можете почитать замечательную книжку Аршинова и Садовского «Коды и математика». Там изложено гораздо больше, чем представлено в этой статье. Если интересует математика кодирования — то поищите «Теория и практика кодов, контролирующих ошибки» Блейхута. А вообще, материалов по этой теме довольно много.

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

Источник

Поделиться с друзьями
admin
Здоровый образ жизни: советы и рекомендации
Adblock
detector