Podręcznik

Zbiór wszystkich słów nad ustalonym alfabetem V oznaczamy symbolem V^* a dowolny niepusty podzbiór L tego zbioru nazywamy językiem. Do zbioru V^* zaliczamy również słowo puste (oznaczane na ogół symbolem ε). Słowo puste ma długość 0. Zbiór V^* jest oczywiście nieskończony ale przeliczalny, mamy bowiem

V^* = {ε} ∪ V ∪ V² ∪ ... ∪ Vⁿ ∪ ...

W zbiorze V^* definiujemy działanie dwuargumentowe $\circ$ V^* × V^* → V^* tzw. konkatenację (ang. concatenation). Jeśli α, β ∈ V^* i α = a₁a₂...a_n β = b₁b₂...b_n to z definicji mamy

a $\circ$ b = a₁a₂...a_n $\circ$ b₁b₂...b_n $\overset{df}=$  a₁a₂...a_nb₁b₂...b_n

Jak widać konkatenacja jest zestawianiem słów np. ala konkatenowane z makota daje alamakota, podobnie kot z let daje kotlet.

Jak łatwo sprawdzić działanie konkatenacji jest łączne, tzn. dla każdego  α, β, γ ∈ V^* mamy (α $\circ$ β) $\circ$ γ = α $\circ$ (β $\circ$ γ). Mamy ponadto dla każdego α ∈ V^*; α $\circ$ ε = ε $\circ$ α = α  zatem słowo puste ε jest jedynką działania $\circ$: V^* × V^* → V^*. Inaczej mówiąc konkatenacja ze słowem pustym dowolnego słowa α ∈ V^* nie zmienia tego słowa. Zbiór ∈ V^* z działaniem konkatenacji $\circ$: V^* × V^* → V jest więc monoidem (czyli półgrupą z jednością). 

Widać natychmiast, że konkatenacja na ogół nie jest działaniem przemiennym w V^*, ale zawsze jest działaniem łącznym, tzn. na ogół x $\cdot$ y ≠ y $\cdot$ x  dla x, y ∈ V^*, ale zawsze tzn. dla każdego x, y, z ∈ V^*, mamy:

(x $\cdot$ y)  $\cdot$ z  = x $\cdot$ (y  $\cdot$ z)

Język to dowolny podzbiór zbioru V^*. Podzbiór ten można definiować na wiele sposobów np. za pomocą wyrażeń regularnych, notacją Backusa-Naura, gramatyką, automatem skończonym itd.. Wszystkie te sposoby poznamy w dalszym ciągu. Istnieje również wiele typów języków m.in. języki regularne, języki bezkontekstowe itd.

Złożeniem dwóch języków K i L, gdzie K, L ⊂ V^* nazywamy język

KL $\overset{df}{=}$ { x, y ∈ <em>V^*</em>;<em> </em>x, <em>y</em> ∈ <em>K</em> oraz <em>y</em> ∈ <em>L</em>}

Potęga języka. Potęgę L^* języka definiujemy indukcyjnie następująco

L⁰ $\overset{df}{=}$ {ε}, L¹ $\overset{df}{=}$ L,  L² $\overset{df}{=}$ LL, Lⁿ⁺¹ $\overset{df}{=}$ LLⁿ, ... 

Potęga liter. Potęgę liter definiujemy indukcyjnie następująco. Niech a będzie dowolną ustaloną literą a ∈ V^* wówczas a⁰ $\overset{df}{=}$ {ε}, a¹ $\overset{df}{=}$ a, a² $\overset{df}{=}$ aa, ..., aⁿ⁺¹ $\overset{df}{=}$ aaⁿ, ... 

Potęga słów. Potęgę słów definiujemy indukcyjnie następująco. Niech w będzie dowolnym ustalonym słowem, w ∈ V^*, wówczas w⁰ $\overset{df}{=}$ {ε}, w¹ $\overset{df}{=}$ w, w² $\overset{df}{=}$ ww, ..., wⁿ⁺¹ $\overset{df}{=}$ wwⁿ, ... 

Domknięcie języka (gwiazdeczka Kleen'a) L^*. Niech V będzie ustalonym alfabetem a L językiem L ⊂ V^*. Domknięciem języka L nazywamy zbiór L^* ⊂ V^*, gdzie

L^{* $\overset{df}{=}$} L⁰ ∪ L¹ ∪ L² ∪ ...,  ∪ Lⁿ ∪ ...

Niech będzie dowolnym ustalonym alfabetem. Wprowadźmy w tym alfabecie metrykę dyskretną ρ_d: V × V → R⁺. Z twierdzenia 1 z Dodatku (p. Metryka Hamminga) wynika, że funkcja ρ_H: Vⁿ × Vⁿ → R⁺ zdefiniowana wzorem: dla każdego y, x ∈ Vⁿ

ρ_H (x, y) $= \displaystyle\sum^n_{i+1}$ ρ_d (x_i, y_i)

jest metryką. Nazywamy ją metryką lub odległością Hamminga w przestrzeni Vⁿ (Vⁿ jest to przestrzeń wszystkich słów o długości n nad alfabetem V). Najczęściej rozważamy metrykę Hamminga dla Vⁿ = {0, 1}. Oczywiście ρ_H: Vⁿ × Vⁿ → N ∪ {0} czyli ρ_H jest funkcją o wartościach w zbiorze liczb całkowitych nieujemnych.

Waga słowa binarnego. Wagą słowa binarnego z przestrzeni {0,1}ⁿ (lub ogólniej z {0,1}^*) nazywamy liczbą jedynek w tym słowie. W ten sposób definiujemy na {0,1}^* funkcję w: {0,1}^* → N ∪ {0}. Oczywiście dla a ∈ {0,1}ⁿ mamy w(a) = ρ_H (0, a) gdzie ρ_H jest metryką Hamminga. Można wyrazić metrykę Hamminga ρ_H w {0,1}ⁿ za pomocą funkcji wagi w.

Niech x, y ∈ {0,1}ⁿ, x = (x₁, x₂, ..., x_n), y = (y₁, y₂, ..., y_n), wówczas mamy

$ρ(x, y)\overset{df}{=} \displaystyle\sum^n_{i=1} ρ_d(x_i, y_j) \overset{df}{=} \displaystyle\sum^n_{i=1} w(x_i-_2y_i) = w(x-y)=w(x+y)$

gdzie x_i - ₂ y_i oznacza różnicę modulo 2, x − y oznacza różnicę modulo 2 po współrzędnych a x + y sumę modulo 2 po współrzędnych.

Niech V₁ oznacza dowolny ustalony zbiór niepusty a V₂ dowolny alfabet. Zbiór V₁ będziemy nazywać zbiorem obiektów kodowanych. Istnieje kilka definicji pojęcia kodu. Najogólniejsza definicja jest taka. Kod to relacja dwuargumentowa k ⊆ V₁ × V^*₁ spełniająca warunek: dla każdego x₁ ∈ V₁ czyli dla każdego elementu ze zbioru obiektów kodowanych istnieje takie x₂ ∈ V^*₂ , że (x_1, x₂) ∈ k. Elementy przeciwdziedziny relacji k czyli elementy zbioru {<em>x</em>₂ ∈ <em>V^*</em>₂; (<em>x</em>₁<em>,x</em>₂) ∈ <em>k</em>} nazywamy w tej sytuacji słowami kodowymi. Jeśli V₂ = {0, 1} to kod nazywamy kodem binarnym lub kodem dwójkowym. W szczególności dowolne odwzorowanie $f$: V₁→V^*₂ jest oczywiście kodem.

Druga definicja kodu nieco bardziej "wymagająca" jest taka: kod to dowolne odwzorowanie $f$: V₁→V^*₂ żądamy przy tym z reguły by funkcja $f$ była różnowartościowa i nie przyjmowała wartości ε i tak najczęściej rozumiane jest pojęcie kodu. W dalszym ciągu pod pojęciem kodu będziemy rozumieć tę najbardziej restryktywną definicję. Sam proces obliczania czy ustalania wartości funkcji $f$ dla elementów zbioru V nazywamy kodowaniem. Wartość $f$(x₁) ∈ V^*₂ jest słowem kodowym, kodującym element x₁ ∈ V₁.

Jeśli istnieje takie n ∈ N, że dla każdego x ∈ V₁ słowo kodowe ma stałą długość n to kod nazywamy kodem o stałej długości (ang fixed length code) lub dokładniej kodem o stałej długości n słowa kodowego. Oczywiście mamy wówczas  $f$: V₁→Vⁿ₂. Najczęściej w systemach cyfrowych mamy do czynienia z takimi właśnie kodami. Przykładem takiego kodu jest znany 8 bitowy kod alfanumeryczny ASCII.

Kod redundancyjny (lub nadmiarowy). Niech  $f$: V₁→V^*₂ będzie kodem. Oznaczmy przez zbiór obiektów kodowanych słowami o długości n ∈ N tzn. niech . Jeśli istnieje takie 1{;()nnAxVfxV=∈∈2 } nN∈, że V czyli zbiór fA jest właściwym podzbiorem zbioru V
to kod nazywamy redundancyjnym lub nadmiarowym. Najkrócej: kodem redundancyjnym nazywamy dowolny kod 2n12:fVV∗→ taki, że funkcja różnowartościowa f nie jest „na”.

Istotą rzeczy jest tu istnienie niepustego słowa w zbiorze V2∗, które nie koduje żadnego obiektu. W powyższej definicji nie interesuje nas czy zbiór obiektów kodowanych jest skończony czy nieskończony.

Kod redundancyjny (lub nadmiarowy) o stałej długości słowa kodowego. Jeśli rozważamy kod o stałej długości (implikuje to skończoność zbioru obiektów kodowanych ) i odwzorowanie f nie jest "na" (czyli jest właściwym podzbiorem zbioru ) to kod taki nazywamy kodem redundancyjnym lub nadmiarowym o stałej długości słowa kodowego. W takim kodzie nie wykorzystujemy wszystkich możliwych słów kodowych o długości n do kodowania obiektów kodowanych. nVVf21:→1V)(1VfnV2

Kody redundancyjne umożliwiają

• 1.sprawdzenie czy dane słowo jest poprawnym słowem kodowym (wykrycie błędu)
• 2. ewentualną korekcję błędu jeśli taki błąd wystąpił na którejś pozycji słowa

Kody redundancyjne znajdują więc zastosowanie wszędzie tam gdzie zależy nam na wykrywaniu lub korekcji błędów występujących w słowie kodowym. Błędy takie pojawiają się czasami podczas transmisji lub przechowywania danych a wynikają z nieuniknionych w realnym środowisku fizycznym szumów i zakłóceń a również co może się zdarzyć z uszkodzenia układów elektronicznych przetwarzających informację. Każdy kod wykrywający błędy i każdy kod korygujący błędy jest kodem nadmiarowym.

Zauważmy jeszcze, że istota kodu polega na wiązaniu z obiektem kodowanym pewnego słowa nad ustalonym alfabetem V. Możemy sobie wyobrażać, że to słowo w pewien sposób opisuje wybrany obiekt, daje jego syntetyczną charakterystykę. Jednak ilość wszystkich słów nad dowolnym alfabetem V jest przeliczalna. Zatem zakładając, że kod jest funkcją różnowartościową dostajemy, że zbiór obiektów kodowanych musi być przeliczalny. Nie ma więc np. kodu kodującego wszystkie liczby rzeczywiste (bo zbiór liczb rzeczywistych nie jest przeliczalny) choć jak pokażemy w dalszym ciągu łatwo zdefiniować kod dla zbioru wszystkich liczb wymiernych. 22

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

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-1...a₁a₀ taki, że

1) a_k,a_k-1...a₁a₀ ∈ {0,1...<em>W</em>-1}, a_k ≠ {0}

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

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

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ć.

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.

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$.

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-1...a₁a₀ $\qquad$i$\qquad$ b = b_kb_k-1,...b₁b₀

to żeby uzyskać sumę s = s_ns_n-1...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>.

Jeśli operujemy słowami kodowymi o stałej długości n i V₂ = {0,1, <span class="equation" style="width:100%;;;;">$W$</span>−1}, gdzie $W$ ∈ {2,3...} to różnych słów kodowych jest $W^n$. Tyle jest n elementowych wariacji z powtórzeniami ze zbioru $W$ elementowego. Zatem zbiór obiektów kodowanych może zawierać co najwyżej $W^n$ elementów. 

Naturalny kod wagowy o stałej długości słowa kodowego to kod, które dla ustalonego $W$ koduje liczby ze zbioru {0,1,2,...,<span class="equation" style="width:100%;;;;">$W^n$</span>−1} w taki sposób, że słowa kodowe należą do iloczynu kartezjańskiego $W^n$. Algorytm tworzenia słów kodowych dla takiego kodu numerycznego polega na uzupełnianiu słowa utworzonego dla naturalnego zapisu wagowego zerami z lewej strony aż do uzyskania wymaganej długości słowa kodowego n.

Z kodami numerycznymi o stałej długości (w szczególności z kodami wagowymi o stałej długości) wagowymi wiążemy pojęcie zakresu zapisu. Zakres zapisu to zbiór liczb reprezentowanych w tym zapisie. Jeśli rozważany kod jest binarny i słowo kodowe n bitowe ma postać a_n-1...a₁a₀ ∈ {0,1}ⁿ to bit nazywamy bitem najbardziej znaczący lub bitem MSB (Most Significant Bit) a bit a₀ bitem najmniej znaczącym lub bitem LSB (Least Significant Bit).

Chcemy przejść z zapisu naturalnego wagowego z wagą W₁ na zapis naturalny wagowy z wagą W₂. Postępujemy według schematu

Zapis a_ka_k-1...a₀ z wagą W_{1 $\overset{(1)}{\longrightarrow}$} wartość m _{$\overset{(2)}{\longrightarrow}$} Zapis a'_ra_r'_-1...a'₀ z wagą W₂ 

(1) Obliczamy po prostu wartość m zgodnie ze wzorem

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

Wygodnie w tym celu posłużyć się schematem Hornera, czyli algorytmem obliczenia wartości wielomianu a_kx^k + a_k-1x^k-1 + ...a₀ w punkcie x.

Schemat Hornera: (...((a_kx + a_k-1)x + a_k-2)x + ... + a₁)x + a₀ = a_kx^k + ... + a₀

(2) Dzielimy z resztą liczbę m przez W₂ otrzymując ciąg reszt a'_ra_r'_-1...a'₀ , dokładniej:

m = m₁⋅ W₂ + a'₀
m₁ = m₂ ⋅ W₂ + a'₁
m₂ = m₃⋅ W₂ + a'₂

.
.

.
m_r-1 = m_r⋅ W₂ + a'_r-1

itd. aż kolejne m_r = 0 co stanowi regułę stopu algorytmu konwersji.

Ostatecznie uzyskujemy zapis a'_ra_r'_-1...a'₀ z wagą W₂

Dokładniej uzupełnienie do W-1 (gdzie W ∈ N, W ≥ 2) słowa a_na_n-1a_n-2...a₀ nad alfabetem {0,1...<em>W−</em>1}. Jest to słowo b_nb_n-1b_n-2...b₀ takie, że a_i + b_i = W−1 dla i=0,1,2,...,n, gdzie dodawanie jest zwykłym dodawaniem ze zbioru liczb całkowitych.

Dla ustalonego n ∈ N ∪ {0} uzupełnienie do W-1 jest więc odwzorowaniem:

U₁: {0,1,...,W−1}ⁿ⁺¹ → {0,1,...,W−1}ⁿ⁺¹

Łatwo sprawdzić, że odwzorowanie to jest idempotentne tzn. U₁ $\circ$ U₁ = id, czyli uzupełnienie do W-1 zastosowane dwa razy do danego słowa daje to samo słowo.

Najważniejsze w praktyce jest uzupełnienie do jedności (ang. 1's complement)

Dokładniej uzupełnienie do W (gdzie W ∈ N, W ≥ 2) słowa a_na_n-1a_n-2...a₀ nad alfabetem {0,1...<em>W−</em>1}. Niech  słowo b_nb_n-1b_n-2...b₀ będzie uzupełnieniem do W-1 słowa a_na_n-1a_n-2...a₀. Potraktujmy słowo b_nb_n-1b_n-2...b₀ jak liczbę w zapisie naturalnym wagowym z wagą W i dodajmy do tej liczby 1 arytmetycznie zaniedbując ewentualne przeniesienie na pozycję n+1 . Uzyskana w ten sposób liczba c_nc_n-1c_n-2...c₀ (w zapisie naturalnym wagowym z wagą W ) nosi nazwę uzupełnienia do W.

Dla ustalonego n ∈ N ∪ {0} uzupełnienie do W jest więc odwzorowaniem:

U₂: {0,1,...,W−1}ⁿ⁺¹ → {0,1,...,W−1}ⁿ⁺¹

Łatwo sprawdzić, że odwzorowanie to jest idempotentne tzn. U_w $\circ$ U_w = id, czyli uzupełnienie do W zastosowane dwa razy do danego słowa daje to samo słowo.

Najważniejsze w praktyce jest uzupełnienie do dwóch (ang. 2's complement)

Dokładniej, omówimy zapis uzupełnień do W (kod numeryczny uzupełnień do W) dla liczb całkowitych n ∈ Z (a więc również ujemnych). Wykorzystamy następujący fakt.

Fakt: Wybierzmy dowolne m ∈ Z, m ≠ 0 i ustalmy wagę W (W ∈ N, W ≥ 2). Wówczas istnieje dokładnie jeden ciąg: a_na_n-1...a₀, gdzie n > 0, taki że dla każdego i = 1,2,...n−1 a_i ∈ {0,1,...W−1}, a_n ∈ {0,1,...W−1}, oraz a_n = 0 i a_n-1 ≠ 0 i lub a_n = 1 taki, że:

$n = -(\text{sgn } a_n)W^n + \displaystyle\sum_{i=0}^{n-1}a_iW^i\qquad$(*)

Dowód: Prosty dowód pozostawiamy Czytelnikowi jako ćwiczenie.

Dla przypomnienia: funkcja sgn: R → {−1,0,1} (tzw. funkcja signum, czyli znak),

zdefiniowana jest dla wzorem: sgn(x) = $\left\{ \begin{array}{ll} { \text{1 gdy x > 0} \\ \text{0 gdy x = 0}\\\text{-1 gdy x < 0}} \end{array} \right.$

Jak widać dla m ∈ N, m ≠ 0 dzięki powyższemu faktowi możemy zdefiniować odwzorowanie $f$: Z \ {0} → <0,W−1>^* wzorem $f$ (m) = a_na_k...a₀ ∈ <0,W−1>^*. Jeśli przyjmiemy dodatkowo, że $f$ (0) = 0 ∈ <0,W−1>^*, to określimy odwzorowanie

$f$ : Z → <0,W−1>^*

nazywane kodem uzupełnień do W.

1. Jeśli a_n = 0 (tzn. słowa kodowe są postaci 0a_n-1a_n-2...a₀) to liczba jest nieujemna

2. Jeśli a_n = W−1 (tzn. słowa kodowe są postaci (W−1)a_n-1a_n-2...a₀) to liczba jest nieujemna

Algorytm obliczania liczby przeciwnej do danej jest w zapisach uzupełnień do W jest następujący. Jeśli m ∈ Z i słowo a_na_n-1...a₀ reprezentuje tę liczbę to słowo reprezentujące −m uzyskujemy jako uzupełnienie do W słowa a_na_n-1...a₀.

Powyżej zdefiniowany kod uzupełnień do W jest kodem o zmiennej długości słowa kodowego. Zdefiniujemy teraz kod uzupełnień do W o stałej długości słowa kodowego.

Wykorzystamy następujący fakt:

Fakt: Wybierzmy dowolne m ∈ <−Wⁿ,Wⁿ−1>, gdzie n > 0 i ustalmy wagę W (W ∈ N, W ≥ 2). Wówczas istnieje dokładnie jeden ciąg: a_na_n-1...a₀, taki że dla każdego i = 1,2...,n, a_i ∈ {0,1,...,<i>W</i>−1} taki, że:

n = −(sgn a_n)Wⁿ + $\displaystyle\sum^{n-1}_{i=0}a_iW^i\qquad$(*)

Dowód: Prosty dowód pozostawiamy Czytelnikowi jako ćwiczenie.

Odwzorowanie $f$ :<−Wⁿ,Wⁿ−1>→<0,W−1>ⁿ zdefiniowane w powyższym twierdzeniu nosi nazwę zapisu uzupełnień do W (o stałej długości słowa kodowego).

Zakres tak zdefiniowanego kodu jest równy oczywiście <−Wⁿ,Wⁿ−1>.

Algorytm obliczania liczby przeciwnej do danej jest w zapisach uzupełnień do W (o stałej długości) jest następujący. Jeśli m ∈ <−Wⁿ,Wⁿ−1> i słowo a_na_n-1...a₀ reprezentuje tę liczbę to słowo reprezentujące  −m uzyskujemy jako uzupełnienie do W słowa a_na_n-1...a₀.

W systemach cyfrowych stosujemy głównie zapis uzupełnień do 2 (ang. two`s complement notation), który nazywany jest również zapisem U2. Jest to obok zapisu NKB najczęściej stosowany w technice mikroprocesorowej kod numeryczny. Popularność zapisu U2 wynika m.in. z faktu, że algorytmy dodawania i odejmowania w U2 dają się zrealizować a sposób naturalny w zwykłym, prostym sumatorze sumującym liczby w kodzie NKB.

W kodzie U2 (o stałej długości słowa n+1) słowo binarne a_na_n-1...a₀ związane jest z reprezentowaną tym słowem liczbą za pomocą wzoru

n = −(sgn a_n)2ⁿ + $\displaystyle\sum^{n-1}_{i=0}a_i2^i$ = −a_n2ⁿ + $\displaystyle\sum^{n-1}_{i=0}a_i2^i$

a zakres reprezentowanych liczb jest równy <−2ⁿ,2ⁿ−1>

Bit a_n nazywamy bitem najbardziej znaczącym lub bitem MSB od ang. Most Significant Bit) a bit a₀ bitem najmniej znaczącym lub bitem LSB od ang. Least Significant Bit.

W zapisie U2, żeby obliczyć –m mając kod U2 liczby m (czyli rozwinięcie, jak czasem mówimy) negujemy wszystkie bity i na najmniej znaczącej pozycji dodajemy arytmetycznie 1 (tzn. z uwzględnieniem przeniesień). Uzyskany wynik, tzn. słowo binarne reprezentuje tzn. jest kodem U2 liczby –m. Jest to bardzo wygodny algorytm ale uwaga –m musi należeć do zakresu zapisu.

Zapis uzupełnień do W-1 służy do zapisywania liczb całkowitych. Jeśli liczba m ∈ Z jest nieujemna, tzn. m ≥ 0, to zapisujemy ją tak:

m = 0a_n-1a_n-2...a₀

gdzie a_n-1a_n-2a...a₀ jest naturalnym zapisem wagowym z wagą W liczby m, a więc:

$m = \displaystyle\sum^{n-1}_{i=0}a_iW^i$.

Jeśli liczba m ∈ Z jest ujemna (lub równa 0), tzn. L ≤ Z, to wstępnie obliczamy jak wyżej słowo kodowe odpowiadające liczbie |m| zapisujemy je tak: |m| = b_nb_n-1b_n-2...b₀ a następnie jako słowo kodowe odpowiadające m przyjmujemy słowo będące uzupełnieniem do W-1 słowa b_nb_n-1b_n-2...b_0.

Jeśli w opisanej wyżej procedurze stosujemy zamiast naturalnego zapisu wagowego z wagą W zapis naturalny wagowy z wagą W o stałej długości n słowa kodowego to uzyskujemy zapis uzupełnień do W-1 ze stałą długością słowa kodowego. Zakres takiego zapisu uzupełnień do jedności jest równy <−Wⁿ+1,Wⁿ−1>.

W systemach cyfrowych wykorzystuje się najczęściej zapis uzupełnień do 1 ze słowem kodowym o stałej długości. Dla takiego zapisu przy słowie o długości n+1 zakres zapisu jest równy <−2ⁿ+1,2ⁿ−1>. Zapis uzupełnień do 1 nazywa się też zapisem U1.

Algorytm obliczania liczby przeciwnej jest w zapisie uzupełnień do W-1 wyjątkowo łatwy. Obliczmy po prostu uzupełnienie do W-1 słowa wejściowego. W przypadku U1 sprowadza się to do zanegowania bitów.

Już wiemy z poprzednich punktów jak można reprezentować liczby naturalne i 0 w systemie cyfrowym oraz jak można reprezentować liczby całkowite czyli mówiąc niezbyt precyzyjnie liczby ze znakiem. Często jednak chcemy reprezentować w systemie cyfrowym ułamki (liczby wymierne) i do tego celu wykorzystujemy koncepcję zapisu stałoprzecinkowego (ang. fixed point notation).

Oczywiście naturalnym pomysłem jest reprezentowanie liczby wymiernej jako pary uporządkowanej liczb całkowitych (m,n), gdzie m, n ∈ Z. Tak czasem się robi ale algorytmy wykonywania działań arytmetycznych (i porównywanie liczb) okazuje się bardziej skomplikowane niż w zdefiniowanym poniżej zapisie stałoprzecinkowym.

Do uwzględnienia znaku można użyć zapisu uzupełnień do W, uzupełnień do W-1 lub zapisu moduł znak. W szczególności możemy użyć zapisu U2 lub U1. Dla ustalenia uwagi zakładamy, że używamy zapisu uzupełnień do W.

Zapis stałoprzecinkowy (uzupełnień do W) ze stałą długością słowa kodowego definiujemy następująco. Będziemy reprezentować liczby ze zbioru A = {−<em>Wⁿ + k</em>⋅<em>W</em>^{−<em>r</em>}; <em>k</em> ∈ < 0, <em>W</em>^{<em>n</em>+<em>r</em>+1}>} (gdzie n ≥ 1, r ≥ 0, n, r ∈ Z). Liczbę n ∈ A reprezentujemy słowem a_na_n-1...a₀a_-1...a_-r (słowem nad alfabetem <0, W−1>) tak by był spełniony wzór

$n = -(\text{sgn } a_n)W^n + \displaystyle\sum_{i=-r}^{n-1}a_iW^i\qquad$(*)

Jeśli założymy, że a_n  ∈ {0,<em>W</em>−1} i a_i  ∈ {0,<em>W</em>−1} to takie słowo a_na_n-1...a₀a_-1...a_-r jest wyznaczone jednoznacznie.

Rys. 1. Rozmieszczenie na osi liczbowej liczb reprezentowanych w zapisie stałoprzecinkowym. Warto zwrócić uwagę na równomierne rozmieszczenie reprezentowanych liczb. ”Skok” czyli odległość sąsiednich liczb wynosi W^−r.

Liczba dodatnia reprezentowana jest więc ciągiem 0a_n-1a_n-2...a₀a_-1...a_-r i możemy zapisać

0a_n-1a_n-2...a₀a_-1...a_{-r = $\displaystyle\sum^{n-1}_{r=-r}a_iW^i$}

a liczba ujemna ciągiem

a_na_n-1a_n-2...a₀a_-1...a_{-r = $-W^n + \displaystyle\sum^{n-1}_{r=-r}a_iW^i$}

gdzie a_n  = W −1.

Dla W=2 czyli dla zapisu binarnego mamy 1 bit znaku, n bitów części całkowitej i r bitów części ułamkowej.

Algorytm obliczania liczby przeciwnej do danej jest identyczny jak w przypadku zapisu uzupełnień do W. W celu znalezienia liczby przeciwnej obliczamy uzupełnienie do W słowa wejściowego.

Analogicznie jak wyżej można zdefiniować zapis stałoprzecinkowy o zmiennej długości słowa kodowego.

Oczywiście zapisy U2, U1 i moduł znak tak jak zdefiniowano je w punktach poprzednich można traktować jako zapisy stałoprzecinkowe z odpowiednio umieszczonym przecinkiem.

Rys. 2. Koncepcja zapisu stałoprzecinkowego

Zapis zmiennoprzecinkowy lub notacja zmiennoprzecinkowa (czasem mówimy zapis zmiennopozycyjny) to jeden z najczęściej stosowanych w mikroprocesorach kodów numerycznych. Angielskie nazwy to floating point notation lub scientific notation.

Zasadniczy pomysł jest bardzo prosty. Liczby bardzo duże i bardzo małe wygodnie jest zapisywać w następującej wykładniczej postaci np. x = −1,5 ⋅ 10¹⁵ lub ogólniej w postaci x = (−1)^s  ⋅ $f$ ⋅ W^e. Możemy zakładać, że W ∈ N, W ≥ 2 ale w praktyce wykorzystujemy W = 10 lub W = 2.

W dalszym ciągu będziemy zakładać, że W = 2 i będziemy rozważać zapis zmiennoprzecinkowy binarny. Liczba s ∈ {0,} reprezentuje znak liczby x. Liczbę $f$ ≥ 0 nazywamy mantysą (lub częścią ułamkową ang. mantissa lub fraction) a liczbę e wykładnikiem (lub cechą ang. exponent). Tak więc liczbę x = (−1)^s  ⋅ $f$ ⋅ W^e możemy reprezentować jako trójkę uporządkowaną (s, $f$, e) czyli trójkę (znak,mantysa,wykladnik).

Oczywiście jeśli nie narzucimy dodatkowych warunków na $f$ i e to takie przedstawienie nie jest jednoznaczne. Liczby $f$ i e muszą być ponadto zapisane w ustalonych kodach numerycznych. Zakładamy w dalszym ciągu, że są to kody numeryczne binarne.

Przedstawienie liczby staje się jednoznaczne jeśli liczba ma tzw. postać znormalizowaną. Mówimy, że liczba reprezentowana w zapisie ma postać znormalizowaną jeśli mantysa $f$ zapisana w zapisie stałoprzecinkowym bez znaku (z przecinkiem za pierwszym bitem) ma postać: 1.ciąg bitów czyli

(jedynka przed przecinkiem jako pierwszy bit, przecinek (czyli kropka), ciąg bitów)

co odpowiada wartości $f$ z przedziału [1,2). Ponieważ liczby pamiętamy w postaci znormalizowanej nie ma potrzeba pamiętania pierwszego bitu mantysy $f$.

Najczęściej zapis zmiennoprzecinkowy używany jest zgodnie ze standardem IEEE 754. Poniżej opiszemy formaty tego standardu dla słów 32 i 64 bitowych.

Rys. 3. Rozmieszczenie na osi liczbowej liczb reprezentowanych w zapisie zmiennoprzecinkowym. Warto zwrócić uwagę na charakterystyczne nierównomierne rozmieszczenie reprezentowanych liczb. Odległość sąsiednich liczb jest najmniejsza w pobliżu zera i rośnie wraz ze wzrostem odległości od 0.

Rys. 4. Format standardu zapisu zmiennoprzecinkowego IEEE 754 dla pojedynczej precyzji (ang. single precision). Słowa są 32 bitowe.

Rys. 5. Format standardu zapisu zmiennoprzecinkowego IEEE 754 dla podwójnej precyzji (ang. double precision). Słowa są 64 bitowe.

Część ułamkowa $f$ zgodnie uwagą o postaci znormalizowanej pozbawiona jest w standardzie IEEE 754 pierwszej 1. Chcąc więc odtworzyć rzeczywistą wartość $f$ należy poprzedzić ciąg bitów $f$ jedynką i odczytać (1.$f$) jako liczbę zapisaną w zapisie stałoprzecinkowym bez znaku.

Z kolei bit znaku s=1 oznacza liczb ujemną a równy 0 liczbę dodatnią.

W dosyć specjalnym kodzie zapisany jest wykładnik e jest to mianowicie tzw. obciążony kod NKB. W ogólnym przypadku dla słowa n bitowego jest to kod numeryczny przyporządkowujący liczbom całkowitym ze zbioru <−2ⁿ⁻¹+1,2ⁿ⁻¹> kolejne słowa kodowe kodu n bitowego NKB. W standardzie IEEE 754 dla słowa 32 bitowego na zapamiętanie e mamy 8 bitów więc stosujemy do kodowania e obciążony 8 bitowy kod NKB.

Ogólnie rzecz biorąc, kod BCD (od ang. Binary Coded Decimal czyli cyfra dziesiętna zakodowana binarnie) to każde odwzorowanie k: {0,1,...9}→{01}ⁿ. Zbiór obiektów kodowanych jest więc zbiorem V₁ = {0,1,...9} cyfr dziesiętnych. Kod BCD można traktować jako kod alfanumeryczny lub kod liczbowy. Kody BCD nazywa się również w literaturze polskiej kodami dwójkowo-dziesiętnymi.

Ponieważ zależy nam na tym, żeby kod był możliwie krótki, kody BCD są z reguły funkcjami k: {0,1,...9}→{01}ⁿ.. Oczywiście nie możemy przyjąć tu krótszych słów kodowych niż 4 bitowe (bo funkcja k nie będzie różnowartościowa) tak więc n ≥ 4.

Wszystkich możliwych kodów 4 bitowych BCD jest bardzo dużo bo tyle ile 10 elementowych wariacji bez powtórzeń ze zbioru 16 elementowego czyli

$\frac{16!}{(16-10)!} = \frac{16!}{6!}$

a różnych kodów BCD n bitowych dla n ≥ 4 mamy tyle ile 10 elementowych wariacji bez powtórzeń ze zbioru 2ⁿ elementowego czyli 

$\frac{2^n!}{(2^n - 10)!}$

Kodów BCD używanych w praktyce jest jednak zaledwie kilka

• kod BCD 8421 – kod naturalny, najbardziej popularny kod BCD.
• kod BCD 2421 tzw. kod Aikena (kod 4 bitowy)
• kod z nadmiarem 3 tzw. kod excess 3 (kod 4 bitowy)
• kod 2 z 5 (kod 5 bitowy)
• kod 1 z 10 (kod 10 bitowy)
• kod Graya z nadmiarem 3 (kod 4 bitowy)
• kod wskaźników cyfrowych 7 –mio segmentowych (kod 7 bitowy)

Kod BCD 8421 jest następujący

0 → 0000
1 → 0001
2 → 0010
3 → 0011
4 → 0100
5 → 0101
6 → 0110
7 → 0111
8 → 1000
9 → 1001

Czterobitowy kod BCD w naturalny sposób umożliwia zapisanie 2 słów kodowych BCD na jednym bajcie. Taką sytuację nazywamy spakowanym kodem BCD. Czasem jednak wygodnie jest w jednym bajcie mieć tylko jedno słowo kodowe BCD na mniej znaczących bitach. Taką sytuację nazywamy nie spakowanym kodem BCD. Kod BCD 8421 w postaci nie spakowanej ma tę zaletę, że słowa kodowe dają się łatwo i w naturalny sposób zastąpić odpowiednimi słowami kodowymi kodu alfanumerycznego ASCII.

Korekcja wyniku dodawania 2 cyfr zapisanych w kodzie BCD 8421. Sumator mikroprocesora z reguły nie ma specjalnego sumatora sumującego w kodzie BCD i używa do sumowania zwykłego sumatora sumującego w kodzie NKB. Dlatego też wynik dodawania 2 cyfr (zwykłego dodawania 4 bitowych słów binarnych) nie musi być wynikiem prawidłowym. Jeśli uzyskany wynik jest mniejszy równy 9 (w kodzie NKB) wynik jest prawidłowy. Jeśli jest większy od 9 lub pojawiło się przeniesienie na pozycję 4-tą (przy numeracji bitów od 0). wynik należy skorygować. Korekcja polega na dodaniu do 4 bitowego wyniku liczby 6.

Kody BCD używane są z reguły połączeniu z innymi kodami numerycznymi np. BCD i naturalny kod dziesiętny. Algorytm dodawania tak zapisanych liczb dziesiętnych kodowanych kodem BCD 8421 polega na kolejnym dodawaniu tetrad (tetrada to słowo 4 bitowe) z ewentualną korekcją wyniku.

W systemach mikroprocesorowych korekcję wyniku przy operacjach w kodzie BCD 8421 realizuje specjalny rozkaz zwykle o mnemonice (czyli symbolicznym oznaczeniu rozkazu) DAA (Decimal Addition Adjust).

Kod BCD excess 3. Kod excess 3 uzyskujemy dodając arytmetycznie 3 (czyli 0011) do słów kodu BCD 8421. Kod BCD excess 3 jest następujący

0 → 0011
1 → 0100
2 → 0101
3 → 0110
4 → 0111
5 → 1000
6 → 1001
7 → 1010
8 → 1011
9 → 1100

Algorytm korekcji wyniku dodawania dla kodu excess 3 jest następujący

• Jeśli nie pojawiło się przeniesienie z danej pozycji, to odejmij 3 od wyniku.
• Jeśli pojawiło się przeniesienie z danej pozycji, to dodaj 3 do wyniku.

Algorytm korekcji jest więc sterowany jest przeniesieniem, jest to proste i wygodne, (tzn. potrzeba korekcji sygnalizowana jest przez przeniesienie). Korekcja przeprowadzana jest „jakby na boku”. Maksymalne opóźnienie tego algorytmu może być znacznie mniejsze niż w przypadku algorytmu dla kodu BCD 8421. Uzasadnienie opisanego algorytmu korekcji pozostawiamy Czytelnikowi.

Kod 2 z 5 . Kod 2 z 5 (należy do grupy kodów BCD i kodów o stałej liczbie jedynek w słowie kodowym tzw. kodów m z n). Słowo kodowe dla kodu 2 z 5 ma długość 5. Zbiór obiektów kodowanych V₁ = {0,1,...9} czyli jest taki jak w każdym kodzie BCD. Alfabet kodu V₂ = {0,1} :

$\left.\begin{array}{}{0 → 00011\\ 1 →00101\\ 2 → 01001\\ 3 → 10001} \end{array}\right\}$ 4 słowa z 1 na pozycji 5

$\left.\begin{array}{}{4 → 00110\\ 5 →01010\\ 6 → 10010} \end{array}\right\}$ 3 słowa z 1 na pozycji 4 i 0 na pozycji 5

$\left.\begin{array}{}{7 → 01100\\ 8 →10100} \end{array}\right\}$ 2 słowa z 1 na pozycji 3 i 0 na pozycji 5 i 4

$\left.\begin{array}{}{9 → 11000} \end{array}\right\}$ 1 słowo z 1 na pozycji 2 i 0 na pozycji 5,4 i 3

Cechy charakterystyczne kodu 2 z 5:

• długość podstawowego słowa kodowego jest zawsze równa 5
• mamy w słowie kodowym stałą równą 2, liczbie jedynek,
• kod 2 z 5 może być traktowany jako alfanumeryczny, jeśli 0,1,...,9 uważamy za symbole lub jako liczbowy, jeśli 0,1,...,9 uważamy za liczby;
• jako kod numeryczny, kod 2 z 5 jest kodem niewagowym;
• 16
• kod 2 z 5 jest kodem redundancyjnym.

Kod 1 z 10. Dla takiego kodu mamy jak dla każdego kodu BCD V1 = {0,1,2,3,...,8,9}

0→1000000000
1→0100000000
2→0010000000
3→0001000000
4→0000100000
5→0000010000
6→0000001000
7→0000000100
8→0000000010
9→0000000001

Zasada tworzenia kolejnych słów kodowych jest przesuwająca się jedynka od lewej strony do prawej. Kod 1 z 10 jest oczywiście przykładem redundancyjnego kodu BCD.

Kody m z n są kodami numerycznymi binarnymi o stałej długości n charakteryzujące się stałą liczbą m jedynek na n pozycjach w słowie kodowym. Przy ustalonym m i n liczba takich słów kodowych jest równa $\left(\! \begin{array}{c} n \\ m \end{array} \!\right) = \frac{n!}{m!(n-m)!}$. Zaletą takich kodów jest stosunkowo łatwa kontrola poprawności słowa kodowego.

Do najprostszych kodów m z n należy kod 1 z n. W rozdziale poświęconym kodom BCD poznaliśmy również kod 2 z 5 oraz kod 1 z 10.

Kod 1 z n. Zbiór obiektów kodowanych to V₁ = {0,1,...,<em>n</em>−1}. Alfabet kodu V₂ = {0,1}. Kod 1 z n to odwzorowanie różnowartościowe V₁ → Vⁿ₂  zadane wzorem:

$V_1 \ni m \to \underset{n}{ \underbrace { 00...0 \underset{m+1}{\underbrace{ 1 } } 0...00} } \in \text{{0,1}}^n$

Czyli m kodujemy za pomocą pojedynczej jedynki umieszczonej na pozycji m + 1 licząc od lewej strony.

Zasada tworzenia kolejnych słów kodowych to przesuwająca się jedynka od lewej strony do prawej.

Zapis resztowy to inaczej zapis rezidualny lub zapis RNS (od ang. Residue Number System). Koncepcja zapisu rezidualnego (lub nieco ogólniej arytmetyki ) pochodzi od A.Svobody i M.Valacha i została podana w pracy zamieszczonej w czeskim czasopiśmie ”Stroje na Zapracovani Informaci” w roku 1955. Niezależnie od A.Svobody i M.Valacha pomysł zapisu rezidualnego podał w 1959 r. H.L.Garner w pracy opublikowanej w IRE Transactions EC-8.

Zapis resztowy umożliwia realizację szybkiej arytmetyki (dokładniej: dodawania, odejmowania i mnożenia) bez propagacji przeniesień. Mnożenia które są dosyć złożonymi działaniami (a np. w cyfrowym przetwarzaniu sygnałów mnożeń wykonujemy bardzo dużo) można jak zobaczymy wykonywać bardzo szybko i prosto. Skomplikowane stają się natomiast w zapisie RNS algorytmy dzielenia i porównania liczb.

Symbolem $[x]_m$ lub x (mod m) będziemy w dalszym ciągu oznaczać resztę z dzielenia liczby x ∈ Z przez liczbę m ∈ N, m ≥ N, m ≥ 2. Potrzebne nam będzie ponadto pojęcie kongruencji. Niech m ∈ N, m ≥ 2, mówimy, że dwie liczby a, b ∈ Z przystają modulo m jeśli dają tę samą resztę z dzielenia przez m. Zapisujemy to pisząc a ≡ b (mod m). Zapis taki nazywamy kongruencją modulo m.

Podstawą zapisu resztowego jest następujące chińskie twierdzenie o resztach.

Dowód: Możemy znaleźć n liczb c₁c₂,...c_n takich, że c_i ∈ $Z{_m}_{_i}$oraz c_i $\otimes _{m_i} \left[ \frac{M}{m_i} \right]_{m_{i}}$ = 1 (lub równoważnie c_i jest elementem odwrotnym do elementu $\left[ \frac{M}{m_i} \right]_{m_i}$ w pierścieniu $Z_{m_{i}}$ czyli c_i = $\left[ \frac{M}{m_i} \right]^{-i}_{m_{i}}$). Łatwo sprawdzić, że k_i = c_i $\frac{M}{m_i}$ i = 1,2,3,...,n spełniają warunek (**). Wynika to z tego, że NWD($m_i,\left[ \frac{M}{m_i} \right]_{m_i}$) = 1.

Niech będzie dana liczba x ∈ Z i niech liczby naturalne m₁,m₂,...m_n większe od jedności będą parami względnie pierwsze. Zapisem resztowym liczby x nazywamy ciąg skończony

$([x]_{m_1},[x]_{m_2},...x]_{m_n})\qquad$(4)

W ten sposób definiujemy kod numeryczny $f:$ → $Z{_{m_1}} \times Z{_{m_2}} \times ... \times Z{_{m_n}}$. Zakres tak zdefiniowanego zapisu RNS jest oczywiście równy .

Dodawanie, odejmowanie i mnożenie liczb w zapisie resztowym jest wykonywane po współrzędnych. Dokładniej, jeśli mamy 2 liczby zapisane w zapisie resztowym $a$ = $([a]_{m_1},[a]_{m_2},[a]_{m_n})$ = $(a_1, a_2,..., a_n)$ i $b = ([b]_{m_1}, [b]_{m_2},..., [b]_{m_n}$ = $(b_1, b_2, ..., b_n)$ to wówczas (jeśli wynik działania należy do zakresu zapisu) algorytmy dodawania, odejmowania i mnożenia dane są wzorami

$a+b=(b_1,b_2,...b_n) + (b_1, b_2, ...,b_n) = (a_1\oplus_{m_1}b_1, a_2\oplus_{m_2}b_2, ... a_n\oplus_{m_n}b_n)\qquad$(5)

$a-b=(b_1,b_2,...b_n) - (b_1, b_2, ...,b_n) = (a_1-_{m_1}b_1, a_2-_{m_2}b_2, ... a_n-_{m_n}b_n)\qquad$(6)

$a \cdot b=(b_1,b_2,...b_n) \cdot (b_1, b_2, ...,b_n) = (a_1\oplus_{m_1}b_1, a_2\oplus_{m_2}b_2, ... a_n\oplus_{m_n}b_n)\qquad$(7)

gdzie $a_i \oplus _{m_i} b_i$, $a_i - _{m_i} b_i$, $a_i \otimes _{m_i} b_i$ są odpowiednio dodawaniem, odejmowaniem i mnożeniem modulo $m_i$.

Konwersja zapis NKB liczby x → na zapis RNS liczby x sprowadza się do obliczenia n reszt z dzielenia liczby x przez moduły m₁, m₂, m₃, ..., m_n.

Konwersja zapis RNS →  zapis NKB jest nieco bardziej złożona. Podamy dwa algorytmy konwersji.

Podstawowy algorytm konwersji jest na ogół formułowany w samym chińskim twierdzeniu o resztach. Przypomnijmy algorytm:

Niech a₁, a₂, ..., a_n będzie zapisem RNS liczby x oraz M = m₁, m₂, ..., m_n.

I. Znajdujemy liczby b_j ∈ Z takie, że:

b_j ⋅ $\frac{M}{m_j}$ = 1 (mod $m_j$) dla j = 1,2,...n).$\qquad$(8)

II. Jeśli x ∈ [0, M], to

x = [a₁ ⋅b₁ ⋅ $\frac{M}{m_1}$ + a₂ ⋅b₂ ⋅ $\frac{M}{m_2}$ + ... +  a_n ⋅b_n$\frac{M}{m_n}$]_M,$\qquad$(9)

a ogólnie, jeśli x ∈ [a, a + m), to

x = a + (a₁ ⋅b₁ ⋅ $\frac{M}{m_1}$ + a₂ ⋅b₂ ⋅ $\frac{M}{m_2}$ + ... +  a_n ⋅b_n − a)(mod M).$\qquad$(10)

Konwersja wykorzystująca „mixed radix representation” (algorytm Garnera).

I. Niech (a₁, a₂, a₃) będzie zapisem RNS liczby x. Definiujemy  $\binom{n}{2}$ stałych c_ij (liczymy je tylko jeden raz – wstępnie).

c_ij ⋅ m_i ≡ 1 (mod m_j) dla  1 ≤ i < j ≤ n,$\qquad$(11)

lub co na jedno wychodzi, poszukujemy odwrotności elementu $[m_i]_{m_j}$ w pierścieniu $Z_{m_j}$, czyli takiego c_ij, że c_ij $\otimes_{m_j}$ m_j = 1 w pierścieniu $Z_{m_j}$.

II. Obliczamy ciąg v_1, v₂,...v_n gdzie v₁ ∈ [0, m_i, −1) będący zapisem mixed radix szukanej liczby x,

v₁ := a₁ (mod m₁)

v₂ := (a₁ − v₁)c₁₂(mod m₂)

v₃ := ((a₁ − v₁)c₁₃−v₁)c₂₃(mod m₃)$\qquad$(12)
.
.
.
v_r := ((u_n − v₁)c_1r − v₂)c_2n − ...− v_r−1)c_r−1,n (mod m_n)

III. Obliczamy

x = v_n ⋅m_n−1 ⋅ ...⋅ m₁  + v_n−1 ⋅m_n−2⋅ ...⋅m₁  +...+ v₃ ⋅m₂ ⋅m₁ + v₂ ⋅m₁ ⋅v₁ $\qquad$(13)

Łatwo zauważyć, że w zapisie RNS złożoność konwersji z RNS → zapis binarny; zapis binarny RNS w pewnym stopniu zależy od wyboru modułów m₁,m₂,m₃,...m_n.

Dla modułów postaci 2^e − 1 konwersja liczby x na jej zapis RNS jest bardzo prosta.

Ogólnie rzecz biorąc, jeśli mamy liczbę x ∈ Z otrzymujemy jej reprezentację resztową przez dzielenie x przez kolejne moduły m_i, co daje ciąg (a₁,a₂,...a_r). Jednak dla modułów postaci 2^e_i − 1, można zrobić tak:

x = a_tA^t + a_t−1A^t−1 +...+ a₁A + a₀$\qquad$(14)

gdzie A = 2^e_i i 0 ≤ a_k < 2^e_j i dla każdego k = 0,1,...t.

Zatem:

u = a₁ + a_t −1 + ... + a₁ + a₀ (mod 2^e_j − 1)$\qquad$(15)

ponieważ A ≡ (mod 2^e_j − 1) i ostatecznie:

u_i = a₁ $\oplus$ a_t −1 $\oplus$...$\oplus$ a₁₀$\qquad$(16)

u_i = a_t + a_t −1 + ... + a₀ (mod (2^e_j − 1))$\qquad$(17)

Zajmijmy się modułami postaci m_j = 2^e_j − 1, gdzie e_j ∈ N, e_j ≥ 2, dokładniej. Pokażemy jakie korzyści wynikają z wyboru modułów m₁,m₂,...m_r tak, by było m_j = 2^e_j − 1, e_j ∈ N, e_j ≥ 2. Zależy nam na tym, żeby były to moduły parami względnie pierwsze. Następujące twierdzenie stanowi kryterium na to, by dwie liczby postaci 2^{$^f$}− 1 i 2^e − 1 były względnie pierwsze.

Dowód: 1. Zauważmy, że zachodzi równość:

((2^e − 1)(mod 2^{$^f$}− 1)) = 2^{e, (mod $^f$)} − 1$\qquad$(18)

Jeśli e ≤ $f$, to jest to oczywiste. Niech e>$f$. Równość (18) jest równoważna do kongruencji

(2^e − 1) ≡ 2^{e (mod $^f$)} − 1 (mod (2^{$^f$}− 1))$\qquad$(19)

i dalej

2^e ≡ 2^{e mod $^f$} (mod (2^{$^f$}− 1))$\qquad$(20)

2^{e(mod $^f$)} 2^{$^f$}...q^{$^f$} ≡ 2^{e mod $^f$} (mod (2^{$^f$}− 1))$\qquad$(21)

ale: 2^{$^f$} ≡ 1 (mod (2^{$^f$}− 1)) zatem prawdziwa jest równość (18).

2. Wracamy do dowodzonej równości. Niech e>$f$ (dla e=$f$ równość jest oczywista) wówczas na mocy (18) i algorytmu Euklidesa NWD(2^e − 1,2^{$^f$}− 1) = NWD(2^{$^f$}− 1,2^{e mod $^f$} − 1).

Kolejno stosujemy wzór (18), czyli obliczamy resztę z dzielenia przez liczbę mniejszą, zauważmy przy tym, że NWD(e, $f$) = NWD($f$,e (mod $f$)).

Postępując zgodnie z algorytmem Euklidesa otrzymamy wreszcie, w kolejnym kroku, iloraz reszt =0.

Będziemy więc mieli: NWD(2^e − 1,2^{$^f$}− 1) = NWD(2^a− 1,2⁰ − 1) = 2^a − 1

oraz  NWD(e, $f$) = NWD(a₀) = a

Wniosek: Liczby 2^e − 1 i 2^{$^f$} − 1 są względnie pierwsze wtedy i tylko wtedy, gdy e i $f$ są względnie pierwsze.

Słowo maszynowe k-bitowe, ogólnie rzecz biorąc może być jednak takie, że 2^k > m_i lub 2^k < m_i . Jeśli moduły dają się zapisać w kodzie NKB na słowie maszynowym to jest to oczywiście wygodne, ale nie jest to niezbędne.

Zasadnicze znaczenie dla szybkości wykonywania działań arytmetycznych w zapisie resztowym mają sposoby wykonywania działań modulo m. Działania modulo m powinny być realizowane za pomocą odpowiednio zaprojektowanych układów.

Uogólnieniem zapisu RNS na liczby zespolone jest zapis resztowy QRNS (Quadratic Residue Numer System)

Kody wagowe ze zmienną wagą lub zapisy ze zmienną podstawą (ang Mixed Radix Notation lub Mixed Radix Representation) to kody liczbowe, zasadniczo służące do reprezentowania (czyli zapisu) liczb ze zbioru N ∪ {0}.

Przypomnijmy podstawowe twierdzenie umożliwiające konstruowanie kodów wagowych. Jest to jednocześnie zasadnicze twierdzenie, na którym opiera się definicja kodów wagowych ze zmienną wagą.

Oznaczmy A_i = {0,1...<em>m_i</em>−1} dla i = 0,1,2 i niech A = $\displaystyle\bigcup^\infty_{i=0}$ A_i oraz

B = A₀ ∪ A₀ × A₁ ∪ A₀ × A₁ × A₂ ∪... ∪ A₀ × A₁ × A₂ × ... × A_k ∪ ...

Odwzorowanie K: N ∪ {0} ∋ m → K(m) = a_ka_k−1...a₁a₀ ∈ B (gdzie a ∈ A_i) określone na zbiorze N ∪ {0} i zdefiniowane w powyższym twierdzeniu nazywamy kodem wagowym ze zmienną wagą lub zapisem wagowym ze zmienną wagą (ang. mixed radix notation) przy czym przyjmujemy K(0) = 0. Ta przejrzysta i prosta definicja wymaga jednak kilku uwag. 

Elementy zbioru A = $\displaystyle\bigcup^\infty_{i=0}$ A_i nazywamy cyframi i często utożsamiamy je, czy wiążemy z pewnymi symbolami np. pisanymi na papierze. Raz więc możemy na element ze zbioru A = $\displaystyle\bigcup^\infty_{i=0}$ A_i patrzeć jak na liczbę raz jak na symbol. Jest to w praktyce dosyć wygodne. Oczywiście byłoby lepiej gdyby A = $\displaystyle\bigcup^\infty_{i=0}$ A_i było zbiorem skończonym. Posługiwanie się nieskończonym zbiorem symboli jest bowiem wysoce niepraktyczne.

Zauważmy, że jeśli ciąg (m_i)^∞_i=0 jest ograniczony to A = $\displaystyle\bigcup^\infty_{i=0}$ A_i jest zbiorem skończonym a więc alfabetem. Ponadto istnieje takie k, że m_i ≤ m_k dla każdego i = 0,1,2... oraz A_i ⊂ A_k = A dla każdego i = 0,1,2.... Istnieje więc taki alfabet A, że odwzorowanie K przyjmuje wartości z A^* a więc kod wagowy ze zmienną wagą jest kodem w sensie przyjętej definicji kodu.

Jeśli ciąg (m_i)^∞_i=0  nie jest ograniczony to  A = $\displaystyle\bigcup^\infty_{i=0}$ A_i = N ∪ {0} a więc A nie jest zbiorem skończonym i formalnie rzecz biorąc zapis wagowy K ze zmienną wagą nie jest kodem w sensie przyjętej definicji. Jeśli jednak użyć jakiegokolwiek pomocniczego kodu numerycznego K^': N ∪ {0} → V^* do zapisywania liczb z ze zbioru A = $\displaystyle\bigcup^\infty_{i=0}$ A_i = N ∪ {0}, gdzie V jest jakimkolwiek alfabetem (np. K^': N ∪ {0} → V^* może być zwykłym zapisem dziesiętnym znanym ze szkoły) to łatwo odwzorowanie  K^': N ∪ {0} ∋ m → K(m) = a_ka_k−1...a₁a₀ ∈ B tak zmodyfikować by uzyskać odwzorowanie będące kodem. Wystarczy przyjąć: 

$\tilde K$: N ∪ {0} ∋ m → $\tilde K$(m) = K^'(a_k), K^'(a_k−1), ...K^'(a₁), K^'(a₀) ∈ (V ∪ {,})^*

Podobnie jak ma to miejsce w zapisie wagowym z ustaloną wagą W, możemy w zapisie ze zmienną wagą reprezentować również liczby ułamkowe „wprowadzając kropkę”.

Zapis ze zmienną wagą jest wykorzystywany w jednym z algorytmów konwersji zapisu RNS na zapis wagowy.

Jeśli zbiorem obiektów kodowanych V₁ jest zbiór znaków to kod $f$: V₁ → V^*₂ (dla ustalonego alfabetu V₂ na ogół binarnego) nazywamy kodem alfanumerycznym (ang. alphanumeric code).

W tym podrozdziale poznamy szereg binarnych kodów alfanumerycznych. Najpopularniejsze binarne kody alfanumeryczne to ośmiobitowy kod ASCII (American Standard Code for Information Interchange) i szesnastobitowy kod Unicode. Są to oczywiście kody o stałej długości słowa kodowego.

Znany każdemu telegrafiście i harcerzowi kod Morse'a jest również kodem alfanumerycznym binarnym ale kodem zmiennej długości. Kody alfanumeryczne ASCII zmiennej długości mają specyficzne zalety opisane bliżej w podrozdziale o kompresji danych.

Kod ASCII został wprowadzony w USA w 1963 roku jako kod 7 bitowy. Kod ASCII w swej podstawowej wersji jest więc w zasadzie 7-mio bitowym kodem ale uzupełnionym z reguły bitem parzystości. Jako kod 8 bitowy ma jednak szereg odmian tzw. wersji narodowych.

Kod ASCII jest równoważny z kodem ISO-7 (ISO to skrót od International Organization for Standardization) . Kod ISO-7 został opisany w normie ISO 646 wydanej w roku 1973. Norma ISO 646 przewiduje wprowadzenie znaków narodowych co wiąże się z rozszerzeniem kodu ASCII do kodu 8 bitowego

ISO-8859-2 to ogólnie już przyjęty standard kodowania polskich liter wg polskich norm PN stanowiący rozszerzenie ASCII.

Kod alfanumeryczny UNICODE jest standardem ISO/IEC-10646. Jest to kod 16 bitowy (pierwsza wersja) lub 31 bitowy (druga wersja). UNICODE umożliwia zapisanie wszystkich znaków z alfabetów narodowych (również cyrylicy, alfabetu chińskiego i alfabetu japońskiego)

Kod ASCII w wersji podstawowej koduje 128 znaków. Pierwsze 33 znaki (uporządkowane wg wartości w kodzie NKB słowa kodowego to tzw. znaki sterujące takie jak CR (Carriage Return czyli „powrót karetki”) lub LF (Line Feed czyli „od nowego wiersza”). Służą one do sterowania systemem drukowania lub wyświetlania znaków. Pozostałe znaki to m.in. małe i duże litery alfabetu angielskiego, cyfry, znaki przestankowe oraz kilka symboli matematycznych takich jak nawiasy i znak równości.

Wykrywanie błędów metodą kontroli parzystości jest najprostszą często stosowaną metodą wykrywania błędów.

Załóżmy, że w systemie cyfrowym chcemy przesyłać dane porcjami za pomocą słów n bitowych. Niech x₁x₂...x_n ∈ {0,1}ⁿ będzie takim n bitowym słowem. Przed wysłaniem uzupełniamy to słowo jeszcze jednym bitem x_n+1 tzw. bitem parzystości przy czym 

x_n+1 = 1 jeśli liczba jedynek w słowie x₁x₂...x_n ∈ {0,1}ⁿ jest nieparzysta 

x_n+1 = 0 jeśli liczba jedynek w słowie x₁x₂...x_n ∈ {0,1}ⁿ jest parzysta

Zatem słowo przesyłane x₁x₂...x_nx_n+1 zawiera zawsze parzystą liczb jedynek. Łatwo sprawdzić, że układ generujący bit parzystości jest n wejściową sumą modulo 2.

x_n+1 = x₁ ⊕ x₂ ⊕ ... ⊕ x_n

Nadajnik wysyła słowo n+1 bitowe x₁x₂...x_nx_n+1 a w odbiorniku dostajemy słowo być może z błędami (przekłamaniami) y₁y₂...y_ny_n+1 ∈ {0,1}ⁿ⁺¹. Sprawdzamy parzystość liczby jedynek w słowie binarnym odebranym y₁y₂...y_ny_n+1. Układ sprawdzający czy liczba jedynek jest parzysta jest n+1 wejściową sumą modulo 2 (por. Rys.2). Jeśli liczba jedynek w słowie y₁y₂...y_ny_n+1 jest parzysta to na wyjściu układu mamy 0 jeśli nieparzysta to 1.

Jeśli wysłaliśmy parzystą liczbę jedynek a otrzymaliśmy w odbiorniku nieparzystą tzn., że podczas przesyłania wystąpił błąd. Sprawdzając parzystość wykryjemy każdą nieparzystą ilość błędów.

Zamiast funkcji x_n+1 = x₁ ⊕ x₂ ⊕ ... ⊕ x_n można wykorzystać funkcję x_n+1 = $\overline{x_{n+1} = x_1 ⊕ x_2 ⊕ ... ⊕ x_n}$, wtedy przesyłane słowo będzie zawierało nieparzystą liczbę jedynek.

Pewną modyfikacją opisanej wyżej koncepcji są kody ze stałą liczbą jedynek m w słowie kodowym o stałej długości n tzw. „kody m z n” (por. podrozdział „kody numeryczne”). Pojedyncza zmiana 0 na 1 lub odwrotnie zmienia w takich kodach „bilans” jedynek i zer” i możemy wykryć błąd.

Rys. 2. Układy sprawdzające parzystość słowa binarnego x₁x₂x₃x₄x₅x₆x₇x₈

Definicja (m,n) kodu i kodu liniowego. Zakładamy, że chcemy przesyłać słowa nad alfabetem GF(p^k) (alfabetem jest ciało skończone mające  p^k elementów, gdzie p jest liczbą pierwszą w szczególności może to być ciało GF(2) = Z₂ = {0,1}. Słowa przesyłane mają długość m, chcemy więc przesyłać słowa z (GF(p^k))^m. Koncepcja kodu wykrywającego lub korygującego błędy polega na wykorzystaniu kodu redundancyjnego $f$GF(p^k))^m → (GF(p^k))ⁿ, gdzie n > m. Taki kod nazywamy (m,n) kodem. Obiektami kodowanymi są tu słowa o długości m nad alfabetem GF(p^k) a słowami kodowymi słowa z (GF(p^k))^m. Zbiory (GF(p^k))^m i (GF(p^k))ⁿ są przestrzeniami liniowymi nad ciałem GF(p^k). Jeśli odwzorowanie $f$GF(p^k))^m → (GF(p^k))ⁿ jest liniowe to kod nazywamy kodem liniowym. 

Liniowość odwzorowania oznacza, że istnieje taka macierz A o współczynnikach w ciele GF(p^k) mająca n wierszy i m kolumn, że dla wektora a ∈ (GF(p^k))^m mamy

$f$(a) = A ⋅ a

gdzie wektor a jest traktowany jako macierz kolumnowa.

Kod wykrywający błędy powinien zachowywać się tak, że gdy odbieramy zamiast słowa kodowego $f$(a) słowo z przekłamaniami na pewnej niewielkiej liczbie co najwyżej r pozycji (oznaczmy to słowo z przekłamaniami przez b_r($f$(a))) to oglądając b_r($f$(a)) będziemy mogli stwierdzić czy nastąpiły przekłamania.

Powiemy, że kod $f$GF(p^k))^m → (GF(p^k))ⁿ wykrywa fakt popełnienia co najwyżej r błędów jeśli dla każdego a ∈ (GF(p^k))^m zmiana cyfr na co najwyżej r pozycjach w słowie kodowym $f$(a) nie powoduje przejścia słowa kodowego w słowo $f$(b) dla pewnego b ∈ (GF(p^k))^m,  a ≠ b.

Praktycznie więc wykrywanie błędu może polegać na porównaniu b_r($f$(a)) z wszystkimi możliwymi słowami kodującymi $f$(c) dla c ∈ (GF(p^k))^m. Jeśli nie stwierdzamy zgodności, to stwierdzamy, że słowo b_r($f$(a)) zawiera przekłamanie.

Kod korygujący błędy powinien zachowywać się tak, że gdy odbieramy zamiast słowa kodowego $f$(a) słowo z przekłamaniami na pewnej niewielkiej liczbie co najwyżej r pozycji (tzn. słowo b_r($f$(a))) to oglądając  b_r($f$(a)) będziemy mogli skorygować błędy (stosując pewien algorytm) uzyskując słowo $f$(a) a więc w konsekwencji stwierdzamy, że zostało nadane słowo a.

Zasadnicza koncepcja na jakiej opierają się kody korekcyjne jest taka: Niech $f$GF(p^k))^m → (GF(p^k))ⁿ będzie (m,n) kodem kodującym słowa o długości m za pomocą słów o długości n, gdzie n > m. Zakładamy, że podczas transmisji słowa $f$(a) o długości m może powstać co najwyżej r błędów. Dla każdego a ∈ (GF(p^k))^m kodujemy przy tym słowo a takim ciągiem a ∈ (GF(p^k))ⁿ , że

$\underset{a,b \in (GF(p^k))^m, a \neq b}{\forall}$ = K($f$(a),r) ∩ K($f$(b),r) = ∅$\qquad$(1)

gdzie K(x,r) oznacza kulę o promieniu r w przestrzeni metrycznej GF(p^k))ⁿ  z metryką Hamminga d_H. Warunek (1) oznacza, że każde dwie kule rodziny kul K($f$(x),r); a ∈ GF(p^k))^m są rozłączne. Jeśli tak jest to aby stwierdzić jaka informacja została nadana wystarczy zastosować do słowa odebranego b_k($f$(a)); a ∈ (GF(p^k))^m regułę decyzyjną d: GF(p^k))ⁿ→GF(p^k))ⁿ  zdefiniowaną wzorem

d(b_r(f(a))) = a 

wtedy i tylko wtedy, gdy

 d_H($f$(a),b_r,$f$(a)) = $\underset{x \in (GF(p^k))^m}{min}${<d<sub><em>d_H</em>(<span class="equation">$f$</span>(<em>x</em>),<em>b_r</em>(<span class="equation">$f$</span>(<em>a</em>)) }$\qquad$(2)

Innymi słowy jako informację nadaną przyjmujemy takie a  (GF ( p^k ))^m , że odebrane słowo b_r (f(a))  (GF( p^k ))ⁿ jest najbliższe f(a) tzn.

_{$\underset{a,b \in (GF(p^k))^m, a \neq b}{\forall}$} d_H (f(a), b)  d_H ( f(x), b)$\qquad$ (3)

Jest oczywiste, że powyższa reguła decyzyjna przy warunku (1) jest poprawna w tym sensie, że pozwala na odtworzenie wiadomości nadanej przy ograniczonej do r ilości błędów transmisji.

Warto zauważyć, że istotą powyższego pomysłu na kod korekcyjny jest to, że wokół każdego słowa kodującego f(a) (gdzie a  (GF ( p^k ))^m ) tworzymy otoczenie (w metryce Hamminga), którego elementy (oprócz f(a)) nie są wykorzystywane do kodowania słów z a  (GF ( p^k ))^m . Możemy jednak odebrać (w wyniku wprowadzenia błędów podczas przesyłania słowa f(a)) dowolny element z tego otoczenia a mimo to nie tracimy orientacji w sytuacji, potrafimy wykryć i skorygować przekłamania.

Kod blokowy. Niech V będzie ustalonym alfabetem. Kodem blokowym nazywamy kod f : V^m  Vⁿ , w którym słowom o długości m (obiektom kodowanym) przyporządkowujemy słowa o długości n, gdzie n  m .

Kod blokowy nazywamy kodem grupowym, jeśli słowa kodowe kodu tworzą grupę addytywną.

Różnych typów kodów korekcyjnych (ang. ECC od Error Correcting Codes) jest dosyć dużo. Z bardziej znanych warto wymienić:

• kody cykliczne (kody CRC - ang. Cyclic Redundancy Check)
• kody Hamminga
• kody Reeda-Solomona
• kody Bose-Chaudhuri-Hocquenghema (kody BCH)

Teraz powiemy co to jest wiadomość jawna, kryptogram (albo szyfrogram) oraz szyfr.

System kryptograficzny lub szyfr to piątka uporządkowana (V₁,V₂ , K , E, D) , gdzie:

• V₁ jest alfabetem, w którym zapisujemy wiadomości jawne, V₁^  $\overset{df}{=}$ M, czyli zbiór wszystkich słów nad alfabetem V₁ jest tzw. przestrzenią wiadomości jawnych (M od ang. message) a każdy element M nazywamy wiadomością jawną lub tekstem jawnym.
• V₂  jest alfabetem, w którym zapisujemy kryptogramy (szyfrogramy) V₂^ $\overset{df}{=}$ C , czyli zbiór wszystkich słów nad alfabetem V₂ jest tzw. przestrzenią wiadomości zaszyfrowanych, czyli, jak mówimy, szyfrogramów (szyfrogram nazywamy też kryptogramem, wiadomością zaszyfrowaną, lub tekstem zaszyfrowanym). Często alfabety V₁ i V₂ są tym samym afabetem.
• K jest dowolnym zbiorem jest to tzw. przestrzeń kluczy (ang. key space), każdy element k  K nazywamy kluczem (lub kluczem szyfrującym). Na ogół K jest zbiorem skończonym ale w definicji ogólnej systemu kryptograficznego nie robimy tego założenia.
• E jest funkcją E : M  K  C , obliczanie wartości funkcji E nazywamy szyfrowaniem, a samą funkcję przekształceniem szyfrującym lub co jest nieco mylące również szyfrem. Wartość E(k, m) nazywamy wiadomością zaszyfrowaną, szyfrogramem, kryptogramem lub tekstem zaszyfrowanym. Sposób obliczania E(k,m) dla danych k,m nazywamy algorytmem szyfrowania.
• D jest funkcją D : C  K  M obliczanie wartości funkcji D nazywamy deszyfrowaniem a samą funkcję D przekształceniem deszyfrującym. Sposób obliczania D(k,m) dla danych k, m nazywamy algorytmem deszyfrowania.

Od systemu kryptograficznego wymagamy by dla każdego klucza szyfrującego k₁  K , istniał klucz deszyfrujący k₂  K taki, że dla dowolnej wiadomości jawnej m zachodzi

 D(k₂ , E(k₁, m))  m .

Istota rzeczy: Każdą wiadomość zaszyfrowaną musimy umieć rozszyfrować, ale być może służy do tego już inny klucz.

Z powyższej definicji wynika, że dla każdego k₁  K , odwzorowanie E(  , k₁ ) : M  C jest funkcją różnowartościową. Oczywiście podobnie odwzorowanie D(  , k₂ ) : E( M , k₁ )  C , (gdzie k₂  K jest kluczem deszyfrującym odpowiadającym kluczowi k₁  K ) jest funkcją różnowarościową.

Z powyższej definicji wynika również, że mówiąc niezbyt precyzyjnie, szyfr to rodzina kodów sparametryzowana kluczem k  K .

Istota rzeczy: Szyfr służy do zastąpienia wiadomości jawnej m kryptogramem c. Celem jest takie przekształcenie postaci wiadomości jawnej, by uzyskać postać nieczytelną dla osób nie dysponujących kluczem deszyfrującym. Realizujemy w ten sposób jeden z zasadniczych celów kryptografii tzw. poufność (ang. confidentiality)

Na ogół im więcej elementów ma zbiór K tym szyfr jest bezpieczniejszy trudniej bowiem dopasować wówczas klucz k do przechwyconego kryptogramu c tak by było metodą przeglądania wszystkich kluczy k czyli za pomocą tzw. ataku brutalnego. D(c, k )  m

Klucz w praktyce to słowo nad jakimś ustalonym alfabetem, na ogół alfabetem, w którym zapisujemy wiadomość jawną, w szczególności może to być alfabet binarny {0,1} i wówczas z reguły K  {0,1}ⁿ dla pewnego n  N lub K  {0,1}^* . Jeśli klucz jest słowem nad ustalonym alfabetem to możemy mówić o długości klucza.

Na ogół im dłuższy jest klucz tym bezpieczniejszy jest system kryptograficzny. Oczywiście technicznie rzecz biorąc klucz może mieć dowolną długość. Istnieją jednak w wielu krajach (np. w USA, Francji czy Iraku) pewne ograniczenia o charakterze prawnym np. 128 bitowe klucze to standard w USA i w Polsce do zakupów sieciowych z kartą kredytową i w transakcjach bankowych.

W powszechnym mniemaniu klucze 128 bitowe uważa się za bezpieczne, ale rzecz jasna taka zasada jest niebezpieczną półprawdą, bowiem klucza nie można rozpatrywać w oderwaniu od systemu kryptograficznego np. 128 bitowy czy nawet 512 bitowy klucz w przypadku szyfru RSA nie jest kluczem bezpiecznym. Przyjmuje się, że dla RSA bezpieczna długość klucza to 1024 bity lub więcej.

Ważna uwaga praktyczna o tajności metod i algorytmów kryptograficznych:

Nigdy nie budujemy bezpieczeństwa systemu na ukrywaniu metody czy algorytmu kryptograficznego. Wprost przeciwnie, algorytm publicznie znany, o którym wiadomo, że był atakowany bez powodzenia, można uznać za pewny i bezpieczny.

Szyfry permutacyjne (ang. transposition ciphers) należą do klasy szyfrów symetrycznych. Załóżmy, że alfabety V₁ i V₂ są takie, że V₁  V₂ $\overset{ozn}{=}$ V , a zbiór kluczy

K = {zbiór wszystkich permutacji zbioru <1,<i>r</i>>}

gdzie r jest ustaloną liczbą naturalną.

Niech m  m₁m₂ ...m_r  M będzie dowolną wiadomością jawną. Dla i  1,2,..., r, m_i V . Oznaczmy przez f blokową funkcję szyfrującą bloki (czyli jednostki tekstu) o długości r

f : V ^r  K  V ^r

a dokładniej

f : V ^r  K  (m, )  f (m, )  m_{ (1)} m_{ (2)} ...m_{ (r )}  c V ^r

Zatem wiadomości jawnej m o długości r przyporządkowujemy kryptogram o długości r ustawiając w pewnej kolejności (wyznaczonej przez permutację ) wyrazy ciągu stanowiącego wiadomość jawną.

Do zapamiętania: Kluczem jest permutacja zbioru <1,r>, gdzie r jest długością jednostki tekstu (bloku).

Prosty szyfr podstawieniowy (ang. simple substitution cipher) to szyfr blokowy o długości bloku 1. Niech V₁ będzie ustalonym alfabetem a f : V₁  V₂ funkcją różnowartościową (z reguły V₁  V₂ ). Jeśli wiadomość jawna m  m₁m₂ ...m_r , to szyfrogram c  f (m₁) f (m₂ )... f (m_r) . Funkcja f jest tu kluczem szyfrującym a f ^1 kluczem deszyfrującym.

Klasycznym przykładem takiego szyfru jest szyfr Cezara,. który będzie omówiony dokładniej w dalszym ciągu podrozdziału.

Polialfabetyczny szyfr podstawieniowy (ang. polyalphabetic substitution cipher) to szyfr blokowy o długości bloku t. Niech V₁ będzie ustalonym alfabetem a f_i : V₁  V₂ , funkcją różnowartościową dla i  1,2,..., t (z reguły V₁  V₂ ). Jeśli wiadomość jawna m  m₁m₂ ...m_t to szyfrogram c  f₁ (m₁ ) f₂ (m₂ )... f_t (m_t ) . Funkcja f₁  f ₂  ... f_t jest tu kluczem szyfrującym a f₁ ^1  f₂ ^1  ... f_t ^1 kluczem deszyfrującym.

Przykład: Rozważmy dla ustalenia uwagi 26 literowy alfabet języka angielskiego V  {<i>a</i>, <i>b</i>, <i>c</i>,..., <i>z</i>} . Klasycznym szyfrem Cezara nazywamy szyfr podstawieniowy, w którym V₁  V₂  V i funkcją definiującą podstawienia jest permutacja  : V  V , gdzie

$\pi = \binom{ \text {a b c d e ... y z}}{ \text {d e f g h ... b c} }$

Jeśli utożsamimy litery z liczbami z pierścienia Z₂₆ na zasadzie a ~ 0, b~1, c~2, d~3, ..., y~24, z~25 , to widać, że:

 (x)  x  3(mod 26)

co odpowiada braniu jako wartości permutacji  liczby – litery znajdującej się o 3 pozycje w prawo (modulo 26) w stosunku do liczby – litery argumentu.

Ogólnie rzecz biorąc, jeśli alfabet V jest n literowy, to możemy V utożsamić z Z_n i zdefiniować permutację  : V  V wzorem:

 (x)  (x  r)(mod n)

Kryptogram wiadomości jawnej m  m₁m₂ m₃ ...m_s otrzymujemy więc jako

 (m₁ ) (m₂ ) (m₃ )... (m_s )

Tak zdefiniowany szyfr, nazywamy szyfrem Cezara z przesunięciem r. Oczywiście r jest kluczem szyfrującym i deszyfrującym jednocześnie. Kluczem w szyfrze Cezara jest więc liczba naturalna ze zbioru Z_n

Przykład: Załóżmy, że m jest licznością alfabetu jawnego V tzn. m  cardV , np. m = 26 w przypadku języka angielskiego.

Identyfikujemy:

a  1 czyli identyfikujemy kolejne litery z kolejnymi liczbami

b  2 naturalnymi ze zbioru {1,2,...,26}

...

z  26

W przypadku alfabetu polskiego liter jest trochę więcej, bo mamy ą, ć, ę, ł, ń, ś , ó, ź. Klucz k  k₁ k₂ ...k_t V ^t , t  N powtarzamy, jeśli trzeba, okresowo.

Szyfr Vigenere`a zadajemy tak: definiujemy odwzorowane f_i : V  V wzorem:

f_i (a) $\overset{df}{=}$ a _m k_i

dla tekstu jawnego m  m₁m₂ ...m_k

$c = f_{[1]_t} (m_1)f_{[2]_t}(m_2)...f_{[k]_t} (m_k)$

Przykład: Okres klucza 5, klucz k = OKRES

m = ENCYKLOPEDIA TECHNIKI
k = OKRESOKRESOKRESOKRESO
                                                      
c = TYUCC ZGJWXLRYXRSENCX

Oczywiście szyfr Cezara jest szczególnym przypadkiem szyfru Vigenere`a.

Szyfry strumieniowe (ang. stream ciphers) są ważną klasą szyfrów z kluczem symetrycznym. Należą do klasy szyfrów blokowych, (z długością bloku =1, a więc oddzielnie szyfrujemy każdą literę tekstu jawnego). Istotą szyfru strumieniowego jest to, że przekształcenie szyfrujące może zmieniać się dla każdego szyfrowanego symbolu.

Szyfry strumieniowe są użyteczne w sytuacji, gdy

• wysokie jest prawdopodobieństwo błędów transmisji, ponieważ w szyfrach strumieniowych nie ma propagacji błędu;
• dane muszą być przesyłane symbol po symbolu (np. szyfrator lub deszyfrator nie ma pamięci).

Zdefiniujemy teraz szyfr strumieniowy formalnie. Niech V₁ i V₂ będą alfabetami. Punktem wyjścia jest blokowa funkcja szyfrująca (szyfrująca bloki o długości 1) E : K V₁  V₂ i blokowa funkcja deszyfrująca (deszyfrująca bloki o długości 1) spełniające warunek:

$\underset{m \in V_1}{\forall} \quad \underset{k_1 \in V_1}{\forall}\quad \underset{k_2 \in K}{\exists}$ D(k₂ , E(k₁ , m)  m .

Tworzymy ciąg (k₁)^{$\underset {_{i=1}}{_{ \infty }}$} , gdzie k_i  K dla każdego i  N . Nazywamy ten ciąg strumieniem kluczy. Definiujemy nowy system kryptograficzny (V₁ ,V₂ , $\tilde K, \tilde E, \tilde D$) następująco. V₁ i V₂ są wprowadzonymi już alfabetami, $\tilde K$ {(<i>k</i>_<i>i</i>)<sup><span class="equation" style="width:100%;;;;">$\underset {_{i=1}}{_{ \infty }}$  ; k_i  K} zbiorem kluczy,  $\tilde E$: $\tilde K$ V₁^*  V₂^* funkcją szyfrującą, dokładniej $\tilde E$ zadane jest wzorem:

$\tilde E$ ((k_i )^{$\underset {_{i=1}}{_{ \infty }}$}, * m₁m₂ ...m_r )  E(k₁, m₁)E(k₂ , m₂ )...E(k_r , m_r )  c₁c₂ ...c_r

$\tilde D$: $\tilde K$ V₂^*  V₁^* funkcją deszyfrującą, dokładniej $\tilde D$ zadane jest wzorem:

$\tilde D$((k_i )^{$\underset {_{i=1}}{_{ \infty }}$} c₁c₂ ...c_r )  D(k₁, c₁)D(k₂ , c₂ )...D(k_r , c_r )  m₁m₂ ...m_r

Taki system kryptograficzny nazywamy szyfrem strumieniowym.

Szyfr Vernama to inaczej szyfr idealny lub szyfr z kluczem jednokrotnym (ang. one pad cipher).

Idealnym z kryptograficznego punktu widzenia jest szyfr z jednokrotnym kluczem losowym generowanym w ciągu prób Bernoulliego. Szyfr z kluczem jednokrotnym charakteryzuje się bezpieczeństwem idealnym, ponieważ przy przechwyceniu szyfrogramu c o określonej długości n prawdopodobieństwo warunkowe wystąpienia danego tekstu jawnego m (długości n) pod warunkiem odebrania c nie zależy od m.

Szczególnym przypadkiem szyfru jednokrotnego jest szyfr Vernama, przekształcający ciągi zerojedynkowe na ciągi zerojedynkowe. Szyfr ten został wynaleziony w 1917 roku przez dwóch Amerykanów: Gilberta S. Vernama (pracującego dla American Telephone and Telegraph Company, w skrócie AT&T) i Josepha O. Mauborgne ( z US Army Signal Corps.)

Rys. 1. Szyfr Vernama. Szyfrowanie: c_i  m_i  k_i . Deszyfrowanie: m_i  c_i  k_i

Algorytm deszyfrowania jest następujący: m_i  c_i  k_i . Jego poprawność wynika z łączności sumy modulo 2 i faktu, że k_i  k_i  0.

Wadą szyfru Vernama jest to, że klucz jest tak długi, jak wiadomość jawna. Jednak w pewnych zastosowaniach użycie klucza jednokrotnego jest uzasadnione (dyplomacja, wojsko).

W praktyce często zastępuje się ciąg losowy k  k₁ k₂ ...k_t  {0,1}^* ciągiem pseudolosowym. Np. mamy do zaszyfrowania tekst jawny (m_i)$^{N_0}_{i=1}$ o długości N₀ , generujemy pseudolosowy ciąg bitów (k_i )$^{N_0}_{i=1}$ i szyfrujemy tekst jawny jako (c_i)$^{N_0}_{i=1}$, gdzie c_i  k_i  a_i dla każdego i i1 i=1,2,..., N₀ .

Szyfr Vernama jest szyfrem strumieniowym. Można go uogólnić z przypadku binarnego na dowolny alfabet skończony zastępując sumę modulo 2 sumą modulo n.

Szyfr RSA jest typowym, najczęściej stosowanym szyfrem z kluczem publicznym. Nazwa RSA pochodzi od nazwisk 3 profesorów z MIT (Massachussets Institute of Technology) R.L.Rivesta, A.Shamira i L.M.Adlemana, którzy w roku 1978 opracowali koncepcję tego szyfru. Szyfr RSA uważany jest za jeden z najbezpieczniejszych, najpewniejszych szyfrów. Używany jest do szyfrowania wiadomości, do tworzenia podpisów cyfrowych oraz dystrybucji kluczy kryptograficznych.

Opiszemy teraz, jak tworzymy system kryptograficzny RSA. Potrzebne nam będzie przy omawianiu szyfru RSA pojęcie funkcji Eulera. Dla danej liczby naturalnej n symbolem  (n) oznaczamy liczbę liczb naturalnych względnie pierwszych z n i mniejszych od n, tzn.  (n)  card{<i>m</i> <font face="Symbol, serif"></font> <i>N</i>; <i>m</i> <font face="Symbol, serif"></font> <i>n</i>, <i>NWD</i>(<i>m</i>, <i>n</i>) <font face="Symbol, serif"></font> 1}. W ten sposób definiujemy funkcję  : N  N , która nazywa się funkcją Eulera. Łatwo można wykazać, że jeśli p jest liczbą pierwszą to  ( p)  p  1 i dla każdego k  N , mamy

 ( p^k )  p^{k 1}( p  1) $\qquad$(1)

Jeśli m i n są względnie pierwszymi liczbami naturalnymi to mamy

 (mn)   (m) (n) $\qquad$(2)

Z (1) i (2) dostajemy, że jeśli n  p₁^k1 p₂^k2  ...  p_r^kr , gdzie p₁, p₂ ,..., p_r są parami różnymi liczbami pierwszymi to

 (n)  p₁^{k1 1} ( p₁  1)  p₂^{k2 1} ( p₂  1)  ...  p_r^{kr 1} ( p_r  1) $\qquad$(3)

Wybieramy teraz dwie duże liczby pierwsze p i q obliczamy iloczyn n=pq oraz wartość funkcji Eulera  (n)  ( p  1)(q  1) . Wybieramy następnie losowo dowolną taką liczbę (n) d  Z_(n) , dla której istnieje element odwrotny e  d ^1 w pierścieniu Z_{ (n)} czyli takie e  Z_{ (n)} by d _{ (n)} e  1 w pierścieniu Z_{ (n)} (oczywiście jest to równoważne temu by znaleźć takie e  Z_{ (n)} , żeby d  e  1 (mod (n)) ). Warunkiem koniecznym i dostatecznym na to by istniał taki element odwrotny jest by NWD( (n), d )  1 . Obliczamy e  d ^1 i ujawniamy parę uporządkowaną (e,n) jako klucz publiczny. Kluczem prywatnym będzie para uporządkowana (d,n).

Tekst szyfrowany, czyli tekst jawny m V₁ ^  np. "ala ma kota" zamieniamy na liczbę całkowitą x np. 10982398.

Podnosimy tę liczbę do ustalonej potęgi e w pierścieniu Z_n ((e,n) jest znane i stanowi klucz publiczny) lub co na jedno wychodzi podnosimy tę liczbę do potęgi e w pierścieniu Z i bierzemy resztę z dzielenia tej liczby przez liczbę n. Tę resztę wysyłamy do adresata.

c  x^e

Adresat podnosi (w pierścieniu Z_n ) uzyskaną liczbę do pewnej potęgi d będącej kluczem tajnym czyli kluczem prywatnym uzyskując wiadomość jawną x.

x  c^d

Wykażemy teraz poprawność RSA. Skorzystamy z następującego lematu będącego konsekwencją chińskiego twierdzenia o resztach.

Lemat: Niech m₁ , m₂ ,..., m_n  N będą parami względnie pierwsze (tzn. NWD(m_i , m _j )  1 dla każdego i, j  1, n ,i  j ) i m_i  2 dla każdego i=1,2,...,n oraz niech a, b będą dowolnymi liczbami całkowitymi czyli a, b  Z .

a  b(mod m_i ) dla każdego i=1,2,...,n wtedy i tylko wtedy gdy a  b(mod m₁  m₂ ... m_n )

Dowód poprawności algorytmu RSA: Z założenia ed  1 (mod  (n)), zatem istnieje takie k  Z , że

ed  1  k  (n)$\qquad$(*)

Załóżmy teraz, że wiadomość jawna m  Z_n jest względnie pierwsza z p, czyli NWD(m, p)  1 . Z małego twierdzenia Fermata mamy wówczas:

m ^p1  1 (mod p) $\qquad$(**)

Podnosząc obie strony kongruencji (**) do potęgi k  (q  1) i mnożąc przez m dostajemy:

m^{1k ( p1)(q1)}  m(mod p)

a więc korzystając z (*) mamy:

m^ed  m(mod p) .

Jeżeli NWD(m, p)  1 , to NWD(m, p)  p . Zatem również mamy wówczas:

m^ed  m(mod p)$\qquad$ (***)

Istotnie, ponieważ m jest podzielna przez p, więc m^ed  0(mod p) i m  0(mod p), i kongruencja (***) zachodzi.

Zatem niezależnie od tego czy NWD(m, p)  1 , czy NWD(m, p)  1 , zawsze mamy

m^ed  m(mod p) .

Podobnie możemy rozumować dla liczby pierwszej q otrzymując

m^ed  m(mod q)

Z lematu dostajemy ostatecznie, że m^ed  m(mod pq) .