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

       Определение. Вес Хемминга ω(сi) кодового слова сi равен числу его не
нулевых компонент. Минимальный вес кода есть минимальный вес ненулевого
кодового слова.
       Определение. Расстоянием Хемминга кодовых слов сi и сj d(сi, сj)
определяется числом координат, в которые слова сi и сj различаются.
       Определение. кодовым расстоянием d(c), по Хеммингу, называется наи-
меньшее из всех расстояний между различными парами кодовых слов, т.е.
d (c) = min d (ci , c j )
      ci ,c j ∈C

      Связь веса с расстоянием: d(x,y)= ω(x+y)
      Если слово α при передаче преобразовалось в слово, отличное от α, то
говорят, что в канале произошли ошибки
      Если i-ая буква слова α отлична от i-ой буквы полученного слова β, то
говорят, что произошла ошибка в i-ом разряде.
      Если полученное слово отличается от переданного в t разрядах, то гово-
рят, что произошло t ошибок.
      Число ошибок, имевших место при передаче, равно расстоянию Хеммин-
га между переданным и принятым словами.
      Для того, чтобы в случае кода с обнаружение ошибок одно кодовое слово
не превратилось в другое, расстояние между разрешенными кодовыми комби-
нациями должно быть тем больше, чем выше кратность обнаруживаемых оши-
бок. Т.к. все расстояния различны –> наиболее критично кодовое расстояние.
      Чем больше d(c), тем больше принятая комбинация будет походить на
переданную, чем на другие разрешенные комбинации.
      Пусть при передаче n символов не более t символов может быть искаже-
но. Тогда, если между ∀ двумя кодовыми словами расстояние больше t =>
ошибка будет обнаружена => d(c)>t или d(c)≥ t+1.
      А для исправления t ошибок необходимо и достаточно, чтобы
∀ωi, ωj H(ωi, t)∩H(ωj, t)=∅ ⇔ d(ωi,ωj)≥2t+1 в соответствии с рисунком 3.4

                                           t
                                                   ωj
                                      ωi       t




                                    рисунок 3.4

     Вопрос: Каким должно быть d(c), чтобы одновременно исправлялись
ошибки кратности g и обнаруживались ошибки кратности 2r?
     d(c) ≥ g+r+1 при r ≥ g
     Определение: Булева функция fc( ~xn n), равная единице на множестве С ко-
довых слов и нулю вне С, называется характеристической функцией двоичного
блочного кода С.
     Примечание: С с характеристической функцией fc( ~xn )=х1⊕х2⊕…⊕хn
     C={α=(α1,…, αn): α1⊕α2⊕…⊕αn=1}

                                                                            19