8.1: Вправи шавлії

Last updated
Save as PDF

Page ID: 64260

\( \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}}\)

1

Створіть (двійковий) код Голая за допомогою конструктора codes.golayCode (). Прочитайте документацію, щоб переконатися, що ви збираєте бінарну версію (не потрійну), і не збираєте розширену версію (яка є типовою).

Використовуйте методи Sage для обчислення довжини, розмірності та мінімальної відстані коду.
Скільки помилок може виявити цей код? Скільки це може виправити?
Знайдіть ненульове кодове слово і введіть три помилки, додавши вектор з трьома одиницями (на ваш вибір), щоб створити отримане повідомлення. Показати, що повідомлення декодовано належним чином.
Утилізуйте свій вибір з попередньої частини, але тепер додайте ще одну помилку. Чи правильно декодується нове отримане повідомлення?

2

Однією з методів поліпшення характеристик коду є додавання загального біта перевірки парності, подібно до єдиного біта перевірки парності коду ASCII, описаного у прикладі\(8.3\). Такі коди іменуються розширеною версією оригіналу.

Побудувати (двійковий) код Голая і отримати матрицю перевірки парності. Використовуйте команди Sage, щоб збільшити цю матрицю, щоб створити нову матрицю перевірки парності, яка має додатковий загальний біт перевірки парності. Ви можете знайти корисні матричні методи .augment () та .stack (), а також конструктори zero_vector () та ones_matrix () (пам'ятаючи, що ми вказуємо двійкові записи як з поля GF (2).)
Створіть розширений код, надаючи збільшену матрицю перевірки парності в конструктор codes.from_parity_check_matrix () і обчислити довжину, розмірність і мінімальну відстань розширеного коду.
Як властивості цього нового коду краще? За якою ціною?
Тепер створіть розширений (двійковий) код Голая з конструктором Sage codes.GolayCode () і правильним ключовим словом для отримання розширеної версії. Якщо пощастить, відсортовані списки ваших кодових слів і кодових слів Sage будуть рівними. Якщо ні, метод лінійного коду.is_permutation_equival () повинен повернути True, щоб вказати, що ваш код і Sage є просто перебудовами один одного.

3

Примітка: Ця проблема знаходиться у відпустці (станом на Sage\(6.7\)), тоді як деякі баггі Sage код для мінімальної відстані коду Хеммінга з'ясовується. Випадок r = 2 видає повідомлення про помилку, а для r > 5 обчислення мінімальної відстані стало нестерпно повільним. Так що трохи складніше зробити розумну здогадку з просто\(3\) випадків.

Дуал\((n,k)\) блокового коду формується як весь набір всіх двійкових векторів, які ортогональні кожному вектору вихідного коду. Вправа 8.6.25 описує цю конструкцію і запитує про деякі її властивості.

Ви можете побудувати дуал коду в Sage за допомогою методу.dual_code (). Побудувати двійкові коди Хеммінга та їх дуали, з параметром r в діапазоні від 2 до 5 включно. Створіть таблицю з шістьма стовпцями (можливо, використовуючи функцію html.table ()), яка\(r\text{,}\) перераховує довжину кодів, розміри оригіналу та подвійного, а також мінімальні відстані оригіналу та подвійного.

Формули гіпотез для розмірності та мінімальної відстані дуалу коду Хеммінга як виразів у параметрі\(r\text{.}\)

4

Код з мінімальною відстанню\(d\) називається ідеальним, якщо кожен можливий вектор знаходиться в межах відстані Хеммінга\((d-1)/2\) від якогось кодового слова. Якщо ми розширимо наше поняття геометрії, щоб врахувати відстань Хеммінга як метрику, то ми можемо говорити про сферу радіуса\(r\) навколо вектора (або кодового слова. Для коду довжини\(n\text{,}\) така сфера буде містити

\[ 1 + {n\choose 1} + {n\choose 2} + \cdots + {n\choose r} \nonumber \]

вектори всередині нього. Для ідеального коду сфери радіуса,\(d\) зосереджені на кодових словах коду, точно розділять весь набір всіх можливих векторів. (Це зв'язок, який означає, що теорія кодування поєднується з проблемами упаковки сфери.)

Наслідком\(k\) того, що код виміру є досконалим, полягає в тому, що

\[ 2^k\left({n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose \frac{d-1}{2}}\right) = 2^n \nonumber \]

І навпаки, якщо код має мінімальну відстань\(d\) і умова вище істинна, то код є ідеальним.

Напишіть функцію Python з назвою is_perfect (), яка приймає лінійний код як вхід і повертає True або False. Продемонструйте свою функцію, перевіривши, що (двійковий) код Голая є ідеальним, а потім використовуйте цикл, щоб переконатися, що (двійкові) коди Хеммінга ідеально підходять для всіх довжин нижче\(32\text{.}\)