Kody i szyfry

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.