Skip to main content
LibreTexts - Ukrayinska

8.10: Шавлія

  1. Last updated
  2. Save as PDF
  • Page ID
    64264

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Sage має повний набір лінійних кодів і безліч методів, які можуть бути використані для їх дослідження.

    Побудова лінійних кодів

    Об'єкт codes може бути використаний для отримання стислого списку доступних реалізованих кодів. Коди типу. і натисніть клавішу Tab і більшість інтерфейсів Sage дасть вам список. Потім ви можете використовувати знак питання в кінці назви методу, щоб дізнатися про різні параметри.

    В якості ілюстрації ми будемо використовувати класичний двійковий\((7,4)\) код Хеммінга. «Двійковий» означає, що у нас є вектори з тільки 0 і 1,\(7\) це довжина і означає, що вектори мають\(7\) координати, і\(4\) це вимір, тобто цей код має\(2^4=16\) вектори, що містять код. Документація передбачає, що ми знаємо кілька речей пізніше в курсі. Ми використовуємо GF (2), щоб вказати, що наш код є двійковим - це матиме більше сенсу в кінці курсу. Другий параметр r, і ми бачимо з формул в документації, що установка r=3 дасть довжину\(7\text{.}\)

    Властивості лінійних кодів

    Ми можемо вивчити код Хеммінга, який ми щойно побудували. Спочатку вимір.

    Код досить малий, щоб ми могли перерахувати всі кодові слова.

    Мінімальна відстань - мабуть, одне з найважливіших властивостей. Коди Хеммінга завжди мають мінімальну відстань,\(d=3\text{,}\) тому вони завжди є єдиним виправленням помилок.

    Ми знаємо, що матриця перевірки парності та матриця генератора корисні для побудови, опису та аналізу лінійних кодів. Імена методів Sage лише трохи загадкові. Sage має широкі процедури для аналізу матриць з елементами з різних полів, тому ми виконуємо більшу частину подальшого аналізу цих матриць в Sage.

    Генераторна матриця тут в тексті має стовпці, які є кодовими словами, а лінійні комбінації стовпців (простір стовпців матриці) - кодові слова. У Sage матриця генератора має рядки, які є кодовими словами, а простір рядків матриці - це код. Отже, ось ще одне місце, де нам потрібно подумки перевести між вибором, зробленим у тексті, і вибором, зробленим розробниками Sage.

    Ось частковий тест, що ці дві матриці правильні, здійснюючи Лемму\(8.27\). Зверніть увагу, що нам потрібно використовувати транспонування матриці генератора, з причин, описаних вище.

    Зверніть увагу, що перевірка на парність може бути не канонічною, а матриця генератора може бути не стандартною. Sage може створити матрицю генератора, яка має набір стовпців, які утворюють ідентифікаційну матрицю, хоча не гарантується, що ці стовпці є першими стовпцями. (Стовпці, а не рядки.) Така матриця вважається систематичною, а метод Sage - .systematic_generator_matrix ().

    Декодування за допомогою лінійного коду

    Ми можемо декодувати отримані повідомлення, що походять з лінійного коду. Припустимо, ми отримуємо довжину\(7\) двійкового вектора r.

    Ми можемо визнати, що сталася одна або кілька помилок, оскільки r не знаходиться в коді, оскільки наступне обчислення не дає нульового вектора.

    Лінійний код має метод.decode. Ви можете вибрати один з декількох різних алгоритмів, тоді як коди Хеммінга мають свій власний алгоритм. Алгоритм за замовчуванням - декодування синдрому.

    Так що, якщо ми готові припустити, що тільки одна помилка сталася (що ми могли б, якщо ймовірність індивідуального введення вектора будучи в помилці дуже низька), то ми бачимо, що помилка сталася в третій позиції.

    Пам'ятайте, що може трапитися так, що було не просто одна помилка. Наприклад, припустимо, що повідомлення було таким же, як і раніше, і помилки сталися в третьому, п'ятому і шостому місцях.

    Потім здається, що ми отримали кодове слово, тому ми припускаємо ніяких помилок взагалі, і декодуємо неправильно.