Facit till rekommenderade uppgifter vecka 6

17.1.1

(i) Det minimala avståndet är 2. Koden upptäcker ett fel och rättar inte något fel. (ii) Det minimala avståndet är 2. Koden upptäcker ett fel och rättar inte något fel. (iii) Det minimala avståndet är 3. Koden upptäcker två fel och rättar ett fel.

17.1.4

Vänsterledet i olikheten räknar hur många positioner x och y skiljer på. Varje gång x_i inte är lika med y_i måste vi ha att antingen z_i skiljer sig från x_i eller från y_i, eftersom vi annars skulle ha x_i=z_i=y_i. Alltså finns det minst lika många positioner som räknas med på höger sida i olikheten. (Dessutom kan z_i skilja sig från både x_i och y_i om dessa är lika, så det är i allmänhet inte en likhet.)

17.2.1

Dimensionen är k=1 och det minimala avståndet är n.

17.2.2

Vi kan ändra ett givet kodord x i noll positioner på 1 sätt, i en position på n sätt och i två positioner på n(n-1)/2 sätt. Antalet element i bollen S₂(x) blir därmed 1 + n + n(n-1)/2 = (n²+n+2)/2. För att vi skall kunna ha en kod E som rättar två fel måste vi ha att |E|(n²+n+2)/2 är mindre än eller lika med 2ⁿ som är det totala antalet möjliga ord. Om längden skall vara n=8 får vi |E| får vara högst 2⁸/((8²+8+2)/2)= 512/74=6 + 34/37 som är lite mindre än 7. Eftersom |E| måste vara ett heltal kan det vara högst 6.

17.3.1

Åtta kodord, 000000, 0110111, 0111100, 0001011, 1110000, 1000111, 1001100, 1111011.

17.3.2

Längden är n=7, dimensionen är k=3, eftersom det finns 2³=8 kodord och det minimala avståndet är 3 eftersom den minsta vikten av något kodord utom noll är tre.

17.3.4

(i) 6. (ii) 10. (iii) Det går att hitta en matris som ger en sådan kod om kolonnerna matrisen alla är nollskilda och olika.

17.4.1

100110, eftersom felet har uppstått i den andra positionen. Syndromet, Hx är 110, som är lika med andra kolonnen i matrisen.

17.4.2

2048=2¹¹, eftersom dimensionen blir 15-4=11. Bara det andra är ett kodord. Det första skall korrigeras i sjätte positionen och det sista skall korrigeras i den trettonde positionen.

17.4.3

(i) 12. (Det är det minsta värde på n så att 256(n+1) är högst 2ⁿ.) (ii) En matris med fyra rader och tolv olika nollskilda kolonner fungerar, exempelvis de tolv första kolonnerna från matrisen i uppgift 17.4.2. (iii) 15. (Det är det minsta värde på n så att 256(n²+n+2)/2 är högst 2ⁿ.)