Уравненията на Mac Williams

[xyz]

За да не стои този форум празен, то предлагам в тази тема да се поместват доказателства на уравненията на Mac Williams - т.е. за връзката на спектъра (тегловното разпределение) на двоичен линеен код и неговия дуален.

Нещо ме мързи да търся формулировката - може би ще редактирам и добавя някой друг път.

[nikko]

А защо само на двоичен код. По-добре да се извеждат и доказват връзките в общия случай, т.е. за линейните кодове над крайното поле [tex]\mathbb{F}_q[/tex]

[xyz]

Ами само двоичния случай, защото:
- q-ичния случай не ми е интересен (все пак пиша във форум, а не енциклопедия)
- нормално е да се очаква, че доказателствата в по-частния случай ще са доста повече

[miloshev1]

може ли някой да ми обясни при: С={00000000, 11001100, 01100110, 00110011, 10101010, 11111111, 01010101, 10011001} как се определя А(0), A(1)...A(8)?

[nikko]

Ами лесно се определя. Намираш теглата (броят на ненулевите координати) на кодовите думи. Или
wt(00000000)=0, wt(11001100)=4, wt(01100110)=4, wt(00110011)=4
wt(10101010)=4, wt(11111111)=8, wt(01010101)=4, wt(10011001)=4
[tex]A_i[/tex] е броя на кодовите думи с тегло i
Така [tex]A_0=A_8=1, A_1=A_2=A_3=A_5=A_6=A_7=0, A_4=6[/tex]
Освен това [tex]\sum\limits_{i=0}^{n}A_i=|C|=2^k[/tex] в нашия случай това е 8.

[xyz]

Понеже днес имам достатъчно време, то реших поне да формулирам неформално какво представляват (това е точната дума - а не формулирами) уравненията на Mac Williams (между другото това е име на жена).

Линеен двоичен код можем да дафинираме като множеството на всички двоични вектори, които се получават като линейни комбинации на k на брой фиксирани двоични вектори с равна дължина n. Под събиране на двоични вектори се разбира да им се приложи побитова операция xor или казано по математически да се съберат вектори с елементи от GF(2) (крайно поле с 2 елемента 0 и 1).
ПРИМЕР:
1010010101
1100101011
==========
0110111110

Тези k вектора се наричат пораждащи за кода, а n се нарича дължина на кода. Това е между другото, защото са само дефиниции.

Ако имаме даден линеен код, то ще дефинираме неговия дуален. Два вектора се наричат ортогонални, ако броят на общите им единици е четен (ще го бележим с [tex]\perp[/tex]). Лесно е да се провери, че ако [tex]a \perp b[/tex] и [tex]a \perp c[/tex], тогава [tex]a \perp (b+c)[/tex] (тук с "+" означаваме въведеното по-горе събиране на вектори). Така, ако даден вектор е перпендикулярен на всички вектори, които пораждат кода, тогава той е перпендикулярен и на всеки друг вектор от кода.

Сега следва да въведем и числата A(0), A(1), ... споменати по-горе от miloshev1. Това представляват бройките на векторите от коде съответно с 0, 1, ... броя единици.

Неформално казано уравненията на Mac Williams ни дават точни уравнения за A-тата на кода с A-тата на неговия дуален код. Казано по друг начин - ако знаем само числата A(0),A(1),..., то по тях чрез явни формули можем да определим съотетните A-та за дуалния код.

В следваща тема се се опитам да дам демонстрация на тези уравнения. Но това ще стане някой друг път...

[grav]

Стара тема, но сега я видях и ми стана интересно. Разрових се от чисто любопитство и намерих това.
http://users.ece.gatech.edu/mbloch/sp10_ece6606/macwilliams.pdf
Очаквах, че доказателството ще е комбинаторно по дух, предполагам, че има и такива, но по горното ми допадна много. По дух е хармоничен анализ, в случая върху крайни групи, и прилича на извода на модулярните свойства на тета функцията (най-известната). Преобразуванието на Адамар(Hadamard) е частен случай на Фурие, лема 1 от файла е формулата на Поасон(Poisson sumation) и т.н. Доста интересно.