Kody i szyfry

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