Oppgave 1
n = 2 00 01 11 10 00 10 11 01 n = 3 000 001 011 010 110 111 101 100 000 001 011 111 101 100 110 010 000 001 101 100 110 111 011 010 000 001 101 111 011 010 110 100 000 010 011 001 101 111 110 100 000 010 011 111 110 100 101 001 000 010 110 100 101 111 011 001 000 010 110 111 011 001 101 100 000 100 101 001 011 111 110 010 000 100 101 111 110 010 011 001 000 100 110 010 011 111 101 001 000 100 110 111 101 001 011 010
Oppgave 2
Hvis vi f.eks. bytter om første og andre bit i hver bitsekvens i rekkefølgen 000 001 011 010 110 111 101 100, får vi rekkefølgen: 000 001 101 100 110 111 011 010. Disse to er dermed ekvivalente. Det finnes 3! = 6 mulige slike ombyttinger. Dermed:
Flg. Gray-koder er ekvivalente: 000 001 011 010 110 111 101 100 000 001 101 100 110 111 011 010 000 010 011 001 101 111 110 100 000 010 110 100 101 111 011 001 000 100 101 001 011 111 110 010 000 100 110 010 011 111 101 001 og flg. Gray-koder er ekvivalente: 000 001 011 111 101 100 110 010 000 001 101 111 011 010 110 100 000 010 011 111 110 100 101 001 000 010 110 111 011 001 101 100 000 100 101 001 011 111 110 010 000 100 110 010 011 111 101 001
Dermed kan vi f.eks. bruke 000 001 011 010 110 111 101 100 og 000 001 011 111 101 100 110 010 som representanter for hver sin ekvivalensklasse.
Oppgave 3
public static int[] gray(int n) { int m = 1 << n; // m lik 2 opphøyd i n int[] a = new int[m]; // tabell for gray-koden for (int k = 1; k < m; k <<= 1) // k = 1, 2, 4, 8, . . . { for (int i = 0, j = 2*k - 1; i < j; i++,j-- ) // j = 1, 3, 7, . . { a[j] = a[i] ^ k; // oppdaterer a[0:k] } } return a; }
Oppgave 4
public static String[] gray(int n) { int m = 1 << n; // m lik 2 opphøyd i n String[] g = new String[m]; // tabell for gray-koden g[0] = ""; // den "tomme" koden for (int k = 1; k < m; k = 2*k + 1) // k = 1, 3, 7, 15, . . { int i = 0, j = k; while (i < j) // oppdaterer g[0:k] { g[j] = g[i] + "1"; j--; // setter 1 bakerst g[i] = g[i] + "0"; i++; // setter 0 bakerst } } return g; // returnerer tabellen med gray-koden }
Med denne metoden vil Programkode 1.7.15 b) skrive ut Gray-koden:
000 100 110 010 011 111 101 001