Podręcznik: Naturalne kody wagowe dla liczb naturalnych i zera

2. Kody numeryczne i arytmetyka cyfrowa

2.2. Naturalne kody wagowe dla liczb naturalnych i zera

Podstawowy fakt z arytmetyki umożliwiający skonstruowanie dużej klasy kodów liczbowych tzw. naturalnych kodów wagowych jest następujący:

Twierdzenie: Dla dowolnej liczby m ∈ N i ustalonego ciągu

$(m_i)^\infty_{i=0}$ , gdzie m_i ∈ {2,3,...} istnieje dokładnie jeden ciąg skończony a_k, a_k-1, ..., a₁, a₀ taki, że

1) $\qquad$ dla każdego i = 0,1,...,k, a_i∈ {0,1...mi -1}, a_k ≠0

2) $\qquad$ m = a_km_k-₁m_k-2 ⋅ ... ⋅ m₀ + a_k-₁m_k-₂m_k-₃ ⋅ ...⋅ m₀ + ...a₂m₁m₀ + a₁m₀ + a₀

Dowód: Prosty dowód pozostawiamy Czytelnikowi (por. też D.E.Knuth [5])

Wniosek: Dla dowolnej liczby m ∈ N i ustalonej liczby W ∈ {2,3} istnieje dokładnie jeden ciąg skończony a_k,a_k-₁...a₁a₀taki, że

1) a_k,a_k-₁...a₁a₀∈ {0,1...W-1}, a_k≠ {0}

2) m= a_kW^k . a_k-1W^k-1+ a₁W + a₀

Powyższy wniosek pozostaje również z pewnymi modyfikacjami prawdziwy dla W = -2 (tzw. zapis minusdwójkowy) i innych wag ujemnych (por. [10]). Wagi ujemne nie mają jednak obecnie większego praktycznego znaczenia

Liczba W nosi nazwę wagi lub podstawy zapisu wagowego (ang. radix). W praktyce na oznaczenie liczb {0,1...W - 1} używamy ustalonych symboli z pewnego równolicznego z {0,1...W - 1} alfabetu V, nazywając je cyframi. Wygodnie jest niekiedy te symbole utożsamiać z liczbą ze zbioru {0,1...W - 1} w tym sensie, że raz traktujemy je jak symbole, raz jak liczby. Możemy też wręcz przyjąć, że V = {0,1...W - 1}.

Odwzorowanie K: N ∪ {0} ∋ m → K(m) = a_ka_k-1...a₁a₀ ∈ V^* określone na zbiorze N ∪ {0} i zdefiniowane w powyższym wniosku nazywamy kodem wagowym z wagą W ≥ 2 przy czym przyjmujemy K(0) = 0.

Typowe najczęściej używane wagi to 2, 8, 10, 16, 26 (26 to liczba małych liter w alfabecie angielskim). Wag W=26 i W=256 używamy w kryptografii do utożsamienia tekstu z liczbą ze zbioru N ∪ {0}.

Zapisy wagowe dla wag 2, 8, 10, 16, noszą następujące nazwy:

W=2, kod NKB - naturalny kod binarny lub zapis dwójkowy naturalny (lub zwykły zapis dwójkowy), mamy dwie cyfry: 0, 1

W=8, zapis oktalny, mamy 8 cyfr 0, 1, 2, 3, 4, 5, 6, 7

W=10, zapis dziesiętny, mamy 10 cyfr 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

W=16, zapis hexadecymalny (lub szesnastkowy) , mamy 16 cyfr 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F (stosujemy dodatkowe cyfry A, B, C, D, E, F)

Jeśli mamy wątpliwości, jakiego zapisu używamy, to po zapisie liczby stosujemy znak spoza alfabetu w jakim zapisujemy liczbę, np.: B – dla zapisu binarnego, O - dla zapisu oktalnego, D - dla zapisu dziesiętnego i H - dla zapisu hexadecymalnego. Czasami z kontekstu wynika jakim zapisem operujemy więc dodatkowe wyjaśnienia nie są potrzebne. Zapis dziesiętny będziemy w dalszym ciągu traktować zwyczajowo jako wyróżniony i z reguły literę D będziemy pomijać.

101(B) lub 101B dla zapisu binarnego oraz 1A2(H) lub 1A2H dla zapisu hexadecymalnego.

Wygodnie jest też ciąg K(m) = a_ka_k-1...a₁a₀ ∈ V^*utożsamiać jeśli trzeba z liczbą m tak jak to zwyczajowo czynimy dla zapisu z wagą W=10 czyli dla dobrze znanego zapisu dziesiętnego.

Zapis binarny : 5= 1001 B, 8= 1000 B, 7=111 B

Zapis hexadecymalny: 8= 8 H, 7=7 H, 15=F H

Kod NKB (naturalny kod binarny) dla zbioru liczb {0,1,...,7}.

Kod NKB (naturalny kod binarny) dla zbioru liczb {0,1,...,7}.

0→0
1→1
1→10
3→11
4→100
5→101
6→110
7→111

Warto podkreślić, że zbiorem obiektów kodowanych jest dla rozważanych w tym punkcie kodów zbiór liczb naturalnych z zerem tzn. N ∪ {0} a więc rozważane kody są kodami numerycznymi. Jednocześnie słowa kodowe mogą być dowolnie długie. Nie są to więc kody ze stałą długością słowa kodowego. Dla ustalonej liczby a ∈ N ∪ {0} i ustalonej wagi W ∈ {2,3...} łatwo można obliczyć długość słowa kodowego l(a) reprezentującego liczbę a. Jeśli a = 0, to l(a) = 1, jeśli a ≠ to

$l(a) = \lfloor log_wa\rfloor+1\qquad$ (*)

gdzie $\lfloor \cdot \rfloor$ R → Z jest tzw. funkcją podłogi (lub jak mówimy krótko podłogą). Jeśli x ∈ R to $\lfloor x \rfloor$ jest największą liczbą całkowitą nie większą od $x$ .

Przykład: Obliczmy korzystając ze wzoru (*) za pomocą ilu bitów zapisujemy w kodzie NKB liczby 2ⁿ + 1, 2ⁿ - 1. Ponieważ log₂2ⁿ = n log10² i funkcja logarytmiczna jest ściśle monotoniczna łatwo obliczamy kolejno:

$l(a) = \lfloor log_22^n\rfloor + 1 = n +1 \\ l(a) = \lfloor log_2(2^n+1)\rfloor + 1 = n +1 \\ l(a) = \lfloor log_2(2^n-1)\rfloor + 1 = n$

gdzie a oznacza słowo binarne reprezentujące liczbę.

Ile cyfr hexadecymalnych potrzeba do zapisu liczby 2ⁿ? Stosując wzór (*) dostajemy

$l(a) = \lfloor \text {log}_{16}2^n\rfloor + 1 = \lfloor n/4 \rfloor +1$ .

Obliczmy korzystając ze wzoru (*) za pomocą ilu cyfr dziesiętnych zapisujemy w naturalnym kodzie wagowym dziesiętnym (czyli jak mówimy krótko w zapisie dziesiętnym) liczby 2ⁿ, dla n=10. Ponieważ log₁₀2ⁿ = n log₁₀2 łatwo obliczamy kolejno:

$l(a) = \lfloor log_{10}2^{10}\rfloor + 1 = \lfloor \text{log}_{10}2\rfloor +1 = 4$ . Podobnie można wykazać, że taka sama liczba cyfr dziesiętnych jest potrzebna do zapisu liczby 2ⁿ+ 1 i 2ⁿ− 1 przy n = 10.

Algorytm dodawania w naturalnym zapisie wagowym z wagą W. Algorytm dodawania w naturalnym zapisie wagowym z wagą W jest w zasadzie identyczny jak w przypadku naturalnego zapisu dziesiętnego. Jeśli dodajemy w naturalnym zapisie wagowym z wagą W 2 liczby a i b reprezentowane słowami

a = a_na_n-₁...a₁a₀ $\qquad$ i $\qquad$ b = b_kb_k-₁,...b₁b₀

to żeby uzyskać sumę s = s_ns_n-₁...s₁s₀ postępujemy tak:

1) Obliczamy s₀=a₀+b₀ (mod W). Jeśli s₀=a₀+b₀ ≥ W to podstawiamy c₁ := 1 a jeśli s₀=a₀+b₀ < W to podstawiamy c₁ := 0

2) Obliczamy s₁=a₁+b₁+c₁ (mod W). Jeśli s₁=a₁+b₁ +c₁ ≥ W to podstawiamy c₂ := 1 a jeśli s₁=a₁+b₁ +c₁ < W to podstawiamy c₂ := 0

.....

i) Obliczamy s_i=a_i+b_i+c_i (mod W). Jeśli s_i=a_i+b_i+c_i ≥ W to podstawiamy c_i+1 := 1 a jeśli s_i=a_i+b_i+c_i < W to podstawiamy c_i+1 := 0

......

n) Obliczamy s_n=a_n+b_n+c_n (mod W). Jeśli s_n=a_n+b_n+c_n ≥ W to podstawiamy c_n+1 := 1 a jeśli s_n=a_n+b_n+c_n < W to podstawiamy c_i+1 := 0.

Algorytm mnożenia w naturalnym zapisie wagowym z wagą W jest w zasadzie identyczny jak w przypadku naturalnego zapisu dziesiętnego ale używamy „tabelki mnożenia” właściwej dla W tzn. używamy „tabelki mnożenia” dla par liczb <0,W−1>×<0,W−1>.

Istota rzeczy: algorytmy dodawania i mnożenia w naturalnych zapisach wagowych pozostają właściwie takie same jak w przypadku dodawania liczb w zapisie dziesiętnym.

Przykład: Mamy 2 liczby w zapisie NKB 10101010a=11111111b=. Stosując opisany algorytm otrzymujemy sumę:

10101010
Suma: 11111111
110101001

Mamy 2 liczby w zapisie NKB a = 1010 b =1111. Stosując opisany algorytm mnożenia otrzymujemy iloczyn:

1010
1111
1010
1010
1010
Iloczyn: 1010
10010110