Методические указания к лабораторным работам по курсу "Дискретная математика". Домашова Д.В - 17 стр.

     код С состоит из всех наборов с нечетным числом единиц.
     d(c)=2 => d(c) ≥t+1 => 1≥ t – обнаружение ошибки.
               d(c) ≥2t+1 => 1/2≥ t => t=0 – исправление ошибки.

                       3.6 Построение линейного кода

      Рассмотрим n-мерное арифметическое линейное пространство GF(2k) над
полем GF(2).
      Векторы в этом пространстве – это всевозможные наборы длиной n из
элементов поля GF(2) (0, 1) с операцией покомпонентного сложения по mod 2.
      Определение: Линейным кодом (n, k) называется линейное k- мерное
подпространство пространства GF(2k)
      Так как GF(2) состоит из двух элементов 0 и 1, то сумма любых кодовых
слов будет кодовым словом, и произведение любого кодового слова на элемент
поля так же будет кодовым словом.
      Множество кодовых векторов двоичного линейного кода одновременно
удовлетворяет и аксиомам группы с операцией сложения векторов.
      Если источник вырабатывает двоичные информационные последователь-
ности длиной k, тогда под кодированием будем понимать взаимно однозначное
отображение множества 2k информационных последовательностей в некоторое
подмножество из 2k кодовых слов длиной n.
      Линейный код можно задать с помощью порождающей матрицы.
      Так как размерность подпространства кода (n, k) равна k, то любое мно-
жество базисных векторов может быть использовано в качестве строк для по-
строения матрицы G(k × n), которая называется порождающей матрицей кода.
      Любое из 2k кодовых слов может быть представлено в виде линейной
комбинации строк из G.
      Можно использовать следующий алгоритм получения кодовых слов: ис-
пользуется отображение.
             С=I*G(k × n),где
      I – информационное слово длины k, которое будет закодировано.
      G – порождающая матрица
      С – получающееся кодовое слово длины n.
      Порождающая матрица является сжатым описанием линейного кода.
      Еще одним способом задания линейных кодов, связанных с предыдущим,
является описание с помощью проверочной матрицы.
      Для этого рассмотрим подмножество V* ортогональное пространству ко-
да V, т.е. множество векторов x=(x1,…,xn)∈GF(2k): x1a1⊕…⊕ xnan=0 для
∀ а=(а1,…,аn) ∈V
Множество векторов подпространства V* образует линейный код, который на-
зывают двойственным коду V, причем множество V* является линейным кодом
(n, n-k)
      Порождающая матрица Н двойственного кода V* называется проверочной
матрицей кода V.


20