Login lub e-mail Hasło   

Kod Gray'a

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/nu(...)ex.html
Wyobraźmy sobie, iż konstruujemy ramię robota. Ramię to ma zataczać kąt 32º (na potrzeby przykładu, w rzeczywistości może to być dowolny kąt) . W przegubie ramienia umies...
Wyświetlenia: 13.689 Zamieszczono 02/11/2006

Wyobraźmy sobie, iż konstruujemy ramię robota. Ramię to ma zataczać kąt 32º (na potrzeby przykładu, w rzeczywistości może to być dowolny kąt). W przegubie ramienia umieszczamy czujnik, który odczytuje położenie ramienia i przekazuje kąt obrotu w postaci 5-bitowego naturalnego kodu binarnego.

00000 ---  0º
00001 ---  1º
00010 ---  2º

...

11110 --- 30º
11111 --- 31º

Na pierwszy rzut oka rozwiązanie to wydaje się całkiem sensowne. Mamy ramię. Mamy czujnik obrotu i mamy kod binarny, za pomocą którego czujnik przekazuje informację o położeniu tegoż ramienia. Dane te komputer sterujący może wykorzystywać do kierowania ruchami robota.

A teraz nadchodzi rzeczywistość. Bity z czujnika nie zmieniają się równocześnie - układ pomiarowy ma luzy. Z tego powodu w pewnych sytuacjach mogą pojawić się nieprawidłowe dane z czujnika. Na przykład wyobraźmy sobie, iż ramię obraca się z położenia 15º do położenia 16º:

01111(2) ---  15º - stan początkowy
11110(2) ---  31º - stan przejściowy, bity środkowe nie zdążyły się jeszcze zmienić
11010(2) ---  26º - stan przejściowy, jeszcze są bity niezmienione
10000(2) ---  16º - stan końcowy, ramię osiągnęło zadane położenie

Zwróć uwagę, iż w podanym przykładzie jeśli odczyt danych z czujnika nastąpi przed ustaleniem się stanów jego bitów (po zaniknięciu luzów w układzie pomiarowym), to odczytana wartość ma niewiele wspólnego z rzeczywistym położeniem ramienia robota. Jeśli program sterujący nie uwzględnia błędnych odczytów, może dojść do bardzo dziwnych rzeczy - np. ramię zacznie oscylować w jedną i w drugą stronę, ponieważ komputer sterujący sądzi, iż jest ono w innym położeniu niż powinno być.

Dlaczego tak się dzieje - po prostu zastosowaliśmy zły kod. Idealny kod pomiarowy powinien zmieniać tylko jeden bit przy przechodzeniu do następnej wartości - nasz zmienia tu wszystkie bity, stąd jeśli zmiana nie nastąpi synchronicznie, mogą pojawić się kłopoty. Taki kod istnieje i nosi nazwę kodu Gray'a.

   
   
   

Kolejne wyrazy kodu Gray'a różnią się od siebie stanem tylko jednego bitu.

 
       

Co nam to da? Bardzo dużo. Przy poprzednim kodzie niepewność odczytu mogła w niekorzystnych warunkach dotyczyć wszystkich bitów słowa kodowego. W przypadku kodu Gray'a niepewność ta dotyczy tylko 1 bitu, gdyż tylko jeden bit zmienia swój stan przy przejściu do następnego słowa kodowego. Zatem przykład może wyglądać następująco:

01000(GRAY) --- 15º - stan początkowy
01000(GRAY) --- 15º - stan pośredni, bity jeszcze się nie ustaliły
11000(GRAY) --- 16º - stan końcowy

W kodzie Gray'a słowa kodowe o wartości 15 (01000) i 16 (11000) różnią się tylko jednym bitem. Zatem nie dojdzie do dużych błędów odczytu położenia.

Gdy już wiemy do czego może służyć kod Gray'a (a zastosowań ma bardzo dużo), przejdziemy do sposobu konstrukcji poszczególnych wyrazów. Podana przez nas metoda tworzy tylko jeden z możliwych kodów Gray'a. Pozostałe uzyskuje się np. przez permutację bitów w słowach kodowych.

   
   
    Wyznaczanie i-tego wyrazu n-bitowego kodu Gray'a
  1. Zapisujemy numer wyrazu kodu Gray'a w naturalnym kodzie dwójkowym na zadanej liczbie bitów. Brakujące bity uzupełniamy bitem 0.
  2. Pod spodem wypisujemy ten sam numer przesunięty w prawo o 1 bit. Najmniej znaczący bit odrzucamy. Na początku dopisujemy bit o wartości 0.
  3. Nad odpowiadającymi sobie bitami wykonujemy operację logiczną XOR. Wynik jest wyrazem w kodzie Gray'a.
 
       

 

Dla przykładu znajdźmy za pomocą tej metody wszystkie 16 wyrazów 4 bitowego kodu Gray'a:

Wyraz 0  Kod dwójkowy 0000 0000
XOR 0000
0000
 Kod Gray'a 0000
Wyraz 1 Kod dwójkowy 0001 0001
XOR
0000
0001
 Kod Gray'a 0001
Wyraz 2 Kod dwójkowy 0010 0010
XOR
0001
0011
Kod Gray'a 0011
Wyraz 3 Kod dwójkowy 0011 0011
XOR
0001
0010
Kod Gray'a 0010
Wyraz 4 Kod dwójkowy 0100 0100
XOR
0010
0110
Kod Gray'a 0110
Wyraz 5 Kod dwójkowy 0101 0101
XOR
0010
0111
Kod Gray'a 0111
Wyraz 6 Kod dwójkowy 0110 0110
XOR
0011
0101
Kod Gray'a 0101
Wyraz 7 Kod dwójkowy 0111 0111
XOR
0011
0100
Kod Gray'a 0100
Wyraz 8 Kod dwójkowy 1000 1000
XOR
0100
1100
Kod Gray'a 1100
Wyraz 9 Kod dwójkowy 1001 1001
XOR
0100
1101
Kod Gray'a 1101
Wyraz 10 Kod dwójkowy 1010 1010
XOR
0101
1111
Kod Gray'a 1111
Wyraz 11 Kod dwójkowy 1011 1011
XOR
0101
1110
Kod Gray'a 1110
Wyraz 12 Kod dwójkowy 1100 1100
XOR
0110
1010
Kod Gray'a 1010
Wyraz 13 Kod dwójkowy 1101 1101
XOR
0110
1011
Kod Gray'a 1011
Wyraz 14 Kod dwójkowy 1110 1110
XOR
0111
1001
Kod Gray'a 1001
Wyraz 15 Kod dwójkowy 1111 1111
XOR
0111
1000
Kod Gray'a 1000

Zbierzmy otrzymane wyniki w tabeli. Kolorem czerwonym zaznaczyliśmy bity, które ulegają zmianie w stosunku do poprzedniego wyrazu.

Lp. Kod binarny Kod Gray'a
0  0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000

Zwróćcie uwagę, iż wyrazy kodu Gray'a tworzą zamknięty pierścień. Ostatni wyraz różni się od pierwszego również tylko jednym bitem. Tego typu kod nazywamy kodem Gray'a odzwierciedlonym binarnie (ang. binary reflected Gray code), ponieważ powstał przez proste przekształcenie kodu dwójkowego.

Przekształcenie kodu dwójkowego w kod Gray'a, jak obserwowaliśmy w poprzednim paragrafie, jest dosyć proste. Równie mało skomplikowana jest operacja odwrotna.  Przeliczenia dokonujemy kopiując najstarszy bit kodu Gray'a do najstarszego bitu kodu binarnego. Pozostałe bity otrzymamy wykonując operację XOR na i-tym bicie kodu Gray'a i (i+1)-bicie wyrazu binarnego. Dla przykładu przeliczmy słowo w kodzie Gray'a 1110 na odpowiadające mu słowo dwójkowe:

Przeliczanie kodu Gray'a na naturalny kod dwójkowy
Operacja Opis
  1 1 1 0
         
  1 ? ? ?
Przepisujemy najstarszy bit z kodu Gray'a do najstarszego bitu słowa dwójkowego. Bity te w obu kodach mają tę samą wartość.
  1 1 1 0
XOR    1    
  1 0 ? ?
Otrzymany bit umieszczamy na pozycji przesuniętej w prawo o jedno miejsce i wykonujemy operację XOR z bitem kodu Gray'a. W ten sposób otrzymujemy kolejne bity kodu dwójkowego. W tym przypadku dostajemy bit o wartości 0.
  1 1 1 0
XOR      0  
  1 0 1 ?
Identyczną operację wykonujemy z poprzednio otrzymanym bitem o wartości 0 otrzymując bit kodu dwójkowego o wartości 1.
  1 1 1 0
XOR        1
  1 0 1 1
Ostatnia operacja daje w wyniku słowo binarne 1011, które posłużyło do utworzenia słowa kodu Gray'a o wartości 1110.

Kod Gray'a jest kodem kombinatorycznym. Poszczególne pozycje bitów nie posiadają ustalonych wag, jak w przypadku opisanych poprzednio kodów binarnych. Wyrazy można tworzyć rekurencyjnie z wyrazów już wcześniej utworzonych wg następującego schematu:

   
   
    Rekurencyjny n bitowy kod Gray'a powstaje w sposób następujący

Definiujemy działania na obiektach używanych przez algorytm:

  • Jeśli L jest listą wyrazów binarnych, to L jest listą tych wyrazów wziętych w odwrotnej kolejności.
    Na przykład
    L = {00,01,11,10}
    L = {10,11,01,00}
    - kolejność odwrotna
  • b+L jest nową listą utworzoną przez dołączenie bitu b na początek wszystkich wyrazów listy L.
    Na przykład
    L = {00,01,11,10} - lista wyrazów 2-bitowych
    0+L = {000,001,011,010} - lista wyrazów 3-bitowych
    1+L = {100,101,111,110} - lista wyrazów 3-bitowych
  • L1 Å L2 jest listą powstałą przez złączenie tych dwóch list.
    Na przykład
    L1 = {000,001,011,010} - lista 4-elementowa
    L2 = {100,101,111,110} - lista 4-elementowa
    L1 Å L2 = {000,001,011,010,100,101,111,110} - lista 8-elementowa

Nowa lista wyrazów n-bitowego kodu Gray'a powstaje wg wzoru rekurencyjnego:

Dla n > 0

Jeśli n = 1, to LGRAY(1) = {0,1}
inaczej LGRAY(n) = 0 + LGRAY(n-1) Å  1 + LGRAY(n-1)

 
       

Wynika z tego, iż nowa lista wyrazów kodu Gray'a powstaje z poprzedniej listy po dodaniu na początku wszystkich wyrazów bitu 0 oraz dołączeniu tej samej poprzedniej listy z odwróconą kolejnością wyrazów i dodanym na początku bitem 1. Poniższy przykład pokaże nam, jak to się odbywa.

 

Utworzymy 4-bitowy kod Gray'a wg opisanej metody rekurencyjnej. Jednakże pójdziemy od dołu do góry, tworząc coraz dłuższe kody wynikowe. Rozpoczynamy od n=1. Dla tego przypadku metoda tworzy listę bezpośrednią:

LGRAY(1) = {0,1}

Teraz tworzymy listę wyrazów kodu Gray'a dla n=2 wykorzystując listę utworzoną dla n=1. Wyrazy tej listy zaznaczyliśmy kolorem czerwonym.

LGRAY(2) = 0 + LGRAY(1) Å  1 + LGRAY(1)

0 + LGRAY(1) = {00,01}
1 +
LGRAY(1) = {11,10}

LGRAY(2) = {00,01} Å  {11,10}
LGRAY(2) = {00,01,11,10}

Wyznaczamy listę 3-bitowego kodu Gray'a na podstawie listy 2-bitowego kodu:

LGRAY(3) = 0 + LGRAY(2) Å  1 + LGRAY(2)

0 + LGRAY(2) = {000,001,011,010}
1 +
LGRAY(2) = {110,111,101,100}

LGRAY(3) = {000,001,011,010} Å  {110,111,101,100}
LGRAY(3) = {000,001,011,010,110,111,101,100}

Podobnie postępujemy dla listy 4-bitowego kodu Gray'a:

LGRAY(4) = 0 + LGRAY(3) Å  1 + LGRAY(3)

0 + LGRAY(3) = {0000,0001,0011,0010,0110,0111,0101,0100}
1 +
LGRAY(3) = {1100,1101,1111,1110,1010,1011,1001,1000}

LGRAY(4) = {0000,0001,0011,0010,0110,0111,0101,0100} Å  {1100,1101,1111,1110,1010,1011,1001,1000}
LGRAY(4) = {0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000}

   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

Program pracuje wg powyższego algorytmu rekurencyjnego tworząc kody Gray'a. Oczywiście zastosowaliśmy kilka usprawnień, których znalezienie i rozpracowanie pozostawiamy ambitnym czytelnikom.

Wydruk z uruchomionego programu
Generacja kodu Gray'a
---------------------
(C)2005 J.Wałaszek
I LO w Tarnowie

Ile bitów (1..16) ? 3

000
001
011
010
110
111
101
100

KONIEC. Naciśnij dowolny klawisz...
Microsoft Visual Basic 2005 Express Edition

 

Borland
Delphi 7.0
Personal
Edition
// Generowanie wszystkich wyrazów kodu Graya
// o zadanej liczbie bitów
//------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//------------------------------------------

program KodGraya;

{$APPTYPE CONSOLE}

// W tablicy WyrazyGraya tworzone będą kolejne
// wyrazy kodowe. Tablica ta musi posiadać tyle
// elementów, ile jest wszystkich wyrazów kodu.

var
WyrazyGraya : array[0..65535] of word;

// Funkcja oblicza potęgę liczby 2
//--------------------------------
function Pot2(n : cardinal) : cardinal;
var
p : cardinal;
begin
p := 1;
while n > 0 do
begin

p := p + p;
dec(n);
end;
Pot2 := p;
end;

// Rekurencyjna procedura generacji wyrazów kodu Graya
//----------------------------------------------------
procedure Gray(n : cardinal);
var
i,p : cardinal;
begin
if
n = 1 then
begin

WyrazyGraya[0] := 0;
WyrazyGraya[1] := 1;
end
else
begin

Gray(n - 1); // wyznaczamy poprzednie wyrazy
p := Pot2(n - 1);
for i := p to p + p - 1 do
WyrazyGraya[i] := p + WyrazyGraya[p + p - i - 1];
end;
end;

// Procedura wyświetlająca zawartość tablicy WyrazyGraya
//------------------------------------------------------
procedure Pisz(n : cardinal);
var
i,j,kg : cardinal;
s : string;
begin
for i := 0 to Pot2(n) - 1 do
begin
s := '';
kg := WyrazyGraya[i];
for j := 1 to n do
begin

s := char(48 + kg mod 2) + s;
kg := kg div 2;
end;
writeln(s);
end;
end;

var
n : cardinal;
begin
writeln('Generacja kodu Gray''a');
writeln('---------------------');
writeln('(C)2005 J.Walaszek');
writeln(' I LO w Tarnowie');
writeln;
write('Ile bitow (1..16) ? '); readln(n);
writeln;
if not(n in [1..16]) then
writeln('Niepoprawna liczba bitow n!')
else
begin

Gray(n); Pisz(n);
end;
writeln;
write('Nacisnij klawisz Enter...'); readln;
end.
Borland
C++ Builder
6.0
Personal
Edition
// Generowanie wszystkich wyrazów kodu Graya
// o zadanej liczbie bitów
//------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//------------------------------------------

#include <iostream>
#include <string>

using namespace std;

// W tablicy WyrazyGraya tworzone będą kolejne
// wyrazy kodowe. Tablica ta musi posiadać tyle
// elementów, ile jest wszystkich wyrazów kodu.

unsigned WyrazyGraya[65536];

// Funkcja oblicza potęgę liczby 2
//--------------------------------
unsigned Pot2(unsigned n)
{
unsigned p;

p = 1;
while(n-- > 0) p += p;
return(p);
}

// Rekurencyjna procedura generacji wyrazów kodu Graya
//----------------------------------------------------
void Gray(unsigned n)
{
unsigned i, p;

if(n == 1)
{
WyrazyGraya[0] = 0;
WyrazyGraya[1] = 1;
}
else
{
Gray(n - 1); // wyznaczamy poprzednie wyrazy
p = Pot2(n - 1);
for(i = p; i < p + p; i ++)
WyrazyGraya[i] = p + WyrazyGraya[p + p - i - 1];
};
}

// Procedura wyświetlająca zawartość tablicy WyrazyGraya
//------------------------------------------------------
void Pisz(unsigned n)
{
unsigned i, j, kg, p;
string s;

p = Pot2(n);
for(i = 0; i < p; i++)
{
s = "";
kg = WyrazyGraya[i];
for(j = 1; j <= n; j++)
{
s = (char)(48 + kg % 2) + s;
kg /= 2;
};
cout << s << endl;
};
}

main()
{
unsigned n;
char z[1];

cout << "Generacja kodu Gray'a\n"
"---------------------\n"
"(C)2005 J.Walaszek\n"
" I LO w Tarnowie\n\n"
"Ile bitow (1..16) ? "
;
cin >> n;
cout << endl;
if((n < 1) || (n > 16))
cout << "Niepoprawna liczba bitow n!";
else
{
Gray(n); Pisz(n);
};
cout << "\n\nNacisnij ENTER...\n";
cin.getline(z,1);
cin.getline(z,1);
}
Microsoft
Visual
Basic 2005
Express
Edition
' Generowanie wszystkich wyrazów kodu Graya
' o zadanej liczbie bitów
'------------------------------------------
' (C)2005 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'------------------------------------------


Option Explicit On

Module
Module1

' W tablicy WyrazyGraya tworzone będą kolejne
' wyrazy kodowe. Tablica ta musi posiadać tyle
' elementów, ile jest wszystkich wyrazów kodu.


Dim WyrazyGraya(65536) As UShort

' Funkcja oblicza potęgę liczby 2
'--------------------------------

Public Function Pot2(ByVal n As UInteger) As UInteger
Dim
p As UInteger

p = 1
While n > 0
p = p + p : n = n - 1
End While
Return
p
End Function

' Rekurencyjna procedura generacji wyrazów kodu Graya
'----------------------------------------------------

Public Sub Gray(ByVal n As UInteger)
Dim i, p As UInteger

If
n = 1 Then
WyrazyGraya(0) = 0
WyrazyGraya(1) = 1
Else
Gray(n - 1) ' wyznaczamy poprzednie wyrazy
p = Pot2(n - 1)
For i = p To p + p - 1
WyrazyGraya(i) = p + WyrazyGraya(p + p - i - 1)
Next
End If
End Sub


' Procedura wyświetlająca zawartość tablicy WyrazyGraya
'------------------------------------------------------

Public Sub Pisz(ByVal n As UInteger)
Dim i, j, kg As UInteger
Dim
s As String

For
i = 0 To Pot2(n) - 1
s = ""
kg = WyrazyGraya(i)
For j = 1 To n
s = Chr(48 + kg Mod 2) + s
kg = kg \ 2
Next
Console.WriteLine(s)
Next
End Sub

Sub Main
()

Dim n As UInteger

Console.WriteLine("Generacja kodu Gray'a")
Console.WriteLine("---------------------")
Console.WriteLine("(C)2005 J.Wałaszek")
Console.WriteLine(" I LO w Tarnowie")
Console.WriteLine()
Console.Write("Ile bitów (1..16) ? ") : n = Val(Console.ReadLine())
Console.WriteLine()
If (n < 1) Or (n > 16) Then
Console.WriteLine("Niepoprawna liczba bitów n!")
Else
Gray(n) : Pisz(n)
End If
Console.WriteLine()
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()

End Sub

End Module
Python
# -*- coding: cp1250 -*-
# Generowanie wszystkich wyrazów kodu Graya
# o zadanej liczbie bitów
#------------------------------------------
# (C)2005 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# im. K. Brodzińskiego
# w Tarnowie
#------------------------------------------

# W tablicy WyrazyGraya tworzone będą kolejne
# wyrazy kodowe. Tablica ta musi posiadać tyle
# elementów, ile jest wszystkich wyrazów kodu.

WyrazyGraya = range(65536)

# Funkcja oblicza potęgę liczby 2
#--------------------------------
def Pot2(n):
p = 1
while n:
p *= 2
n -= 1
return p

# Rekurencyjna procedura generacji wyrazów kodu Graya
#----------------------------------------------------
def Gray(n):
if n == 1:
WyrazyGraya[0] = 0
WyrazyGraya[1] = 1
else:
Gray(n - 1) # wyznaczamy poprzednie wyrazy
p = Pot2(n - 1)
for i in range(p, 2 * p):
WyrazyGraya[i] = p + WyrazyGraya[2 * p - i - 1]

# Procedura wyświetlająca zawartość tablicy WyrazyGraya
#------------------------------------------------------
def Pisz(n):
for i in range(Pot2(n)):
s = ""
kg = WyrazyGraya[i]
for j in range(n):
s = chr(48 + kg % 2) + s
kg //= 2
print s

print "Generacja kodu Gray'a"
print "---------------------"
print "(C)2005 J.Walaszek"
print " I LO w Tarnowie"
print
n = int(raw_input("Ile bitow (1..16) ? "))
print
if (n < 1) or (n > 16):
print "Niepoprawna liczba bitow n!"
else:
Gray(n); Pisz(n)
print
raw_input("Nacisnij klawisz Enter...")
JavaScript
<html>
<head>
</head>
<body>
<div align=
"center">
<form style="BORDER-RIGHT: #ff9933 1px outset;
PADDING-RIGHT: 4px;
BORDER-TOP: #ff9933 1px outset;
PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px;
BORDER-LEFT: #ff9933 1px outset;
PADDING-TOP: 1px;
BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66"
name="frmkody">
<h3 style=
"text-align: center">
Rekurencyjne wyznaczanie wyrazów<br>
n-bitowego kodu Gray'a
</h3>
<p style=
"TEXT-ALIGN: center">
(C)2005 mgr Jerzy Wałaszek&nbsp;&nbsp; I LO w Tarnowie
</p>
<hr>
<div align=
"center">
<table border=
"0" cellpadding="4" style="border-collapse: collapse">
<tr>
<td align=
"right">Liczba bitów n (1...16) =</td>
<td>
<input value=
"4" name="inp_n" size="10" style="text-align: right">
</td>
</tr>
</table>
</div>
<p style=
"TEXT-ALIGN: center">
<input onclick=
"main();" type="button" value="Oblicz wyrazy kodu Gray'a"
name="B13">
</p>
<p id=
"out_t" style="TEXT-ALIGN: center">...</p>
</form>

<script language=
"javascript">

// Generowanie wszystkich wyrazów kodu Graya
// o zadanej liczbie bitów
//------------------------------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//------------------------------------------

// W tablicy WyrazyGraya tworzone będą kolejne
// wyrazy kodowe. Tablica ta musi posiadać tyle
// elementów, ile jest wszystkich wyrazów kodu.

var WyrazyGraya = new Array();

// Funkcja oblicza potęgę liczby 2
//--------------------------------
function Pot2(n)
{
var p;

p = 1;
while(n-- > 0) p += p;
return(p);
}

// Rekurencyjna procedura generacji wyrazów kodu Graya
//----------------------------------------------------
function Gray(n)
{
var i,p;

if(n == 1)
{
WyrazyGraya[0] = "0";
WyrazyGraya[1] = "1";
}
else
{
Gray(n - 1); // wyznaczamy poprzednie wyrazy
p = Pot2(n - 1);

// Uwaga - bardzo ważna jest kolejność tych pętli !!!

for(i = p; i < p + p; i ++)
WyrazyGraya[i] = "1" + WyrazyGraya[p + p - i - 1];

for(i = 0; i < p; i++)
WyrazyGraya[i] = "0" + WyrazyGraya[i];
};
}

// Procedura wyświetlająca zawartość tablicy WyrazyGraya
//------------------------------------------------------
function Pisz(n)
{
var i,p,t;

t = "";
p = Pot2(n);
for(i = 0; i < p; i++) t += WyrazyGraya[i] + " ";
document.getElementById("out_t").innerHTML = t;
}

function main()
{
var n;

n = parseInt(document.frmkody.inp_n.value);
if(isNaN(n) || (n < 1) || (n > 16))
document.getElementById("out_t").innerHTML =
"<font color=Red><b>Niepoprawna ilość bitów</b></font>";
else
{
Gray(n); Pisz(n);
};
}

</script>
</div>
</body>
</html>



Dokument ten rozpowszechniany jest zgodnie z zasadami licencji

GNU Free Documentation License.

Podobne artykuły


16
komentarze: 5 | wyświetlenia: 9006
9
komentarze: 0 | wyświetlenia: 2784
49
komentarze: 18 | wyświetlenia: 64978
37
komentarze: 9 | wyświetlenia: 28520
17
komentarze: 4 | wyświetlenia: 14183
15
komentarze: 5 | wyświetlenia: 32761
13
komentarze: 2 | wyświetlenia: 22961
12
komentarze: 3 | wyświetlenia: 29779
12
komentarze: 2 | wyświetlenia: 18506
11
komentarze: 2 | wyświetlenia: 33152
11
komentarze: 1 | wyświetlenia: 86405
11
komentarze: 1 | wyświetlenia: 10475
10
komentarze: 1 | wyświetlenia: 34971
10
komentarze: 5 | wyświetlenia: 20414
 
Autor
Artykuł

Powiązane tematy






Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska