La Codifica dell'Informazione: Introduzione

Cosa Sono i Numeri e il Concetto di Numero

I numeri sono concetti astratti usati per descrivere quantità, grandezze, o posizioni in una sequenza. Il concetto di numero ha una lunga evoluzione storica e filosofica. Inizialmente, i numeri erano strettamente legati al conteggio di oggetti fisici: 1 mela, 2 mele, 3 mele, e così via.

Il concetto di numero si è evoluto per rispondere a diverse esigenze matematiche e fisiche. Oggi i numeri rappresentano non solo quantità, ma anche relazioni, posizioni, soluzioni di equazioni e molto altro.

I numeri naturali (rappresentati dal simbolo $\N$) sono i più semplici e si usano principalmente per contare. La loro nozione può essere definita formalmente attraverso gli assiomi di Peano¹, introdotti dal matematico italiano Giuseppe Peano nel 1889.

Si elencano ora gli assiomi di Peano:

1. Esistenza di un numero naturale iniziale

• 0 è un numero naturale.
• Formalmente: $ 0 \in \mathbb{N} $.

2. Successore

• Ogni numero naturale ( n ) ha un successore, denotato $ S(n) $, che è anch’esso un numero naturale.
• Formalmente: Se $ n \in \mathbb{N} $, allora $ S(n) \in \mathbb{N} $.

3. Iniettività del successore

• Numeri naturali distinti hanno successori distinti. Se due numeri hanno lo stesso successore, allora devono essere uguali.
• Formalmente: Se $ S(n) = S(m) $, allora $ n = m $.

4. 0 non è successore di alcun numero

• 0 non è il successore di nessun numero naturale.
• Formalmente: Non esiste alcun $ n \in \mathbb{N} $ tale che $ S(n) = 0 $.

5. Assioma di induzione

• Se un insieme $ A \subseteq \mathbb{N} $ contiene 0, e se contiene il successore di ogni elemento che contiene, allora $ A $ contiene tutti i numeri naturali.
• Formalmente: Se $ 0 \in A $ e $ n \in A \Rightarrow S(n) \in A $, allora $ A = \mathbb{N} $.

Significato degli assiomi

• Assioma 1: Stabilisce che il numero iniziale è 0.
• Assioma 2: Introduce il concetto di successore, che ci permette di generare tutti i numeri naturali partendo da 0.
• Assioma 3: Garantisce che il successore di un numero è unico.
• Assioma 4: Stabilisce che 0 non è il successore di nessun numero.
• Assioma 5: Fornisce il principio di induzione matematica, fondamentale per le dimostrazioni in matematica.

Gli assiomi di Peano formalizzano la nozione intuitiva di numero naturale e stabiliscono le basi della teoria dei numeri. Grazie a essi, possiamo definire e lavorare con i numeri naturali in maniera rigorosa e consistente. Gli assiomi di Peano forniscono le fondamenta logiche per sviluppare concetti più avanzati, come l’aritmetica e l’algebra.

Gli assiomi di Peano forniscono le regole per costruire i numeri naturali, mentre per rappresentare e utilizzare i numeri in contesti pratici o formali (ad esempio, nell’informatica, nella logica formale o in linguaggi formali come i linguaggi di programmazione) abbiamo la necessità di una codifica.

I Concetti alla Base della Codifica

Alfabeto

Prima di introdurre il concetto di codifica è necessario definire il concetto di codice e di alfabeto. In particolare definiamo l’alfabeto $A$ come un’insieme:

$ A = \{s_{1},s_{2},…,s_{b}\} $ con $ b \in \N $

dove $s_{i}$ con $i \in [1,b]$ è un simbolo dell’alfabeto. Si definisce cardinalità dell’alfabeto il numero di simboli che lo compongono.

Esempi di alfabeto sono:

• l’alfabeto che struttura il sistema di numerazione arabo, definito come segue:

  $ A = \{0,1,2,3,4,5,6,7,8,9\} $;

• l’alfabeto che struttura il sistema di numerazione romano, definito come segue:

  $ A = \{I, V, X, L, C, M, D\} $;

• l’alfabeto latino, definito come segue:

  $ A = \{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\} $;

• l’alfabeto greco, definito come segue:

  $ A = \{\alpha,\beta,\gamma,\delta,\epsilon,\zeta,\eta,\theta,\iota,\kappa,\lambda,\mu,\nu,\xi,\omicron,\pi,\rho,\sigma,\tau,\upsilon,\phi,\chi,\psi,\omega\} $;

ecc.

Nulla vieta di costruire un alfabeto con simboli a piacimento. Anche il seguente alfabeto, a cardinalità uno, è valido:

$ A = \{|\} $²

In questo caso l’unico simbolo ammissibile è $|$.

Codice

Combinando i simbili di un dato alfabeto con opportune regole si può costruire la parola di un codice. Un codice si struttura quindi con parole costruite partendo dai simboli di un dato alfabeto.

I numeri naturali possono essere rappresentati dal codice costruito partendo dall’alfabeto del sistema di numerazione arabo:

$\N = \{0,1,2,3,4,5,6,7,8,9,10,11,12,…\}$

Partendo invece dall’alfabeto latino e possibile costruire il codice che contiene le parole della lingua italiana, inglese ecc.

Codifica

La codifica è una relazione di associazione. Ad esempio la seguente codifica associa le parole del codice dei numeri naturali alle parole del codice della lingua italiana.

$ 1 ⇒ uno $

$ 2 ⇒ due $

$ … $

$ 12 ⇒ dodici $

$ … $

Si evidenzia come una codifica ci consente di relazionare la parola di un determinato codice con la parola di un altro codice.

Un codice è detto a lunghezza fissa se il numero di simboli che compone ogni parola di codice è costante, altrimenti si dice a lunghezza variabile.

I codici e le codifiche numeriche si classificano poi in codici posizionali e non posizionali. Nei codici posizionali l’informazione si ricava attraverso una relazione algebrica.

Codifica di un Numero Naturale

La Codifica Naturale

La codifica naturale è una codifica posizionale utilizzata per rappresentare i numeri naturali. In particolare, nei codici posizionali, dato un alfabeto

$ A = \{s_{1},s_{2},…,s_{b}\} \ con \ b \in \N $

definiamo base la cardinalità dell’alfabeto.

Una parola di codice di lunghezza $n \in \N$ in codifica natuale in base $b$ è costruita come segue:

$P = a_{n-1}…a_{1}a_{0}$ con $a_i$ e $i \in [0, n-1]$ uno qualsiasi dei simboli di $A$

Il suo valore si ottiene attraverso la formula:

$1.)\ valore(P) = a_{n-1}\cdot b^{n-1} + … + a_{1}\cdot b^{1} + a_{0}\cdot b^{0}$

Di seguito la tabella con i codici posizionali di uso comune.

Si suppone ora di voler convertire la seguente parola $P = 1101$³ in codifica naturale rispettivamanete dalla base 2, 8, 10 e 16 alla base 10. Per far ciò si utilizza la formula $1.$ ottenendo per la base 2:

$valore(P) = 1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0 = 8 + 4 + 0 + 1 = 13$

La stessa parola di codice espressa in base 8 invece ha valore:

$valore(P) = 1\cdot 8^3+1\cdot 8^2+0\cdot 8^1+1\cdot 8^0 = 512 + 64 + 0 + 1 = 577$

Da notare che se $P$ è espressa in base 10 la conversione produce:

$valore(P) = 1\cdot 10^3+1\cdot 10^2+0\cdot 10^1+1\cdot 10^0 = 1000 + 100 + 0 + 1 = 1101$

ottenendo la stessa parola di codice.

In base 16, invece, si ottiene:

$valore(P) = 1\cdot 16^3+1\cdot 16^2+0\cdot 16^1+1\cdot 16^0 = 4096 + 256 + 0 + 1 = 4353$

Quindi la stessa parola di codice ha valore differente se espressa in basi differenti.

Per convertire invece un parola di codice in codifica naturale dalla base 10 ad una qualsiasi altra base utilizziamo il metodo delle divisioni ripetute.

Ad esempio, per converitire la parola $P = 125$ dalla base 10 alla base 2 si utilizza il seguente algoritmo:

• si divide $125$ per $2$ e si registra il resto;
• il quoziente ottenuto lo si divide nuovamente per $2$ ripetendo la procedura del punto precedente;
• si itera fino a raggiungere come quoziente $0$ con resto $1$
• il numero binario cercato si ottiene dai resti ottenuti posizionati in ordine inverso.

La parola di codice cercata è $P=1111101$.

Codifica Naturale in Base 2: Proprietà

Si analizzano ora alcune proprietà dei numeri in codifica naturale in base 2.

È immediato osservare che se un numero ha come cifra meno significativa⁴ uno $0$ allora è pari altrimenti è dispari.

Un ulteriore proprietà interessante è lo shift a sinistra o destra. Questa operazione consiste nell’aggiugere uno $0$ a destra del numero (shift a sinistra) oppure nell’eliminare la cifra meno significativa del numero (shift a destra). Nel primo caso l’operazione consiste nel moltiplicare il numero espresso in base 10 per $2$, nel secondo, invece, nel dividere per $2$ con arrotondamento per difetto.

Ad esempio il numero $101$ in base 2 corrisponde in base 10 a $5$. Con lo shift a sinistra otteniamo $1010$ che equivale in base 10 a $10$. Con lo shift a destra otteniamo $10$ che in base 10 equivale a $2$.

È evidente che se effetuiamo uno shift a sinistra aggiungendo $1$ stiamo moltiplicando per $2$ e sommando $1$ il numero espresso in base 10.

L’operazione di padding consiste nell’aggiungere $0$ a sinistra del numero. In questo caso il valore del numero rimane inalterato.

Operatore Modulo

L’operazione $m\ mod\ p$ (dove $mod$ è l’operatore modulo) restituisce il resto $r$ della divisione intera di $m$ per $p$ se e solo se $\exist q \in \Z$ tale che $m = p \cdot q + r$ dove $q$ (quoziente) e $r$ (resto) sono interi.

Aritmetica Binaria

Si introducono ora alcune operazioni aritmetiche binarie di base.

Le operazioni aritmetiche elencate successivamente avvengono in modulo $2^n$ poichè le parole di codice hanno lunghezza $n$.

È sottointeso che i numeri sono espressi in base 2.

Somma

Regole di addizione.

Si supponga di voler effettuare la somma tra $1011$ e $1010$, applicando le regole di addizione si ottiene:

Sottrazione

Regole di sottrazione.

Si supponga di voler effettuare la differenza tra $1101$ e $1010$, applicando le regole di sottrazione si ottiene:

Complemento

Regole di complementazione.

Si supponga di voler complementare il numero $1011$, applicando le regole di complementazione si ottiene:

Esercizi

1. Le seguenti parole di codice sono valide se espresse in codifica naturale in base 2?

• $00000$
• $10000$
• $00100$
• $00200$
• $00001$
• $11111$
• $22222$

2. Le seguenti parole di codice sono valide se espresse in codifica naturale in base 8?

• $00000$
• $10000$
• $22222$
• $77777$
• $76543210$
• $876543210$

3. Le seguenti parole di codice sono valide se espresse in codifica naturale in base 10?

• $1234567890$
• $90000$
• $1234567890A$
• $A1234$
• $AAAAA$

4. Le seguenti parole di codice sono valide se espresse in codifica naturale in base 16?

• $1234567890$
• $90000$
• $1234567890A$
• $A1234$
• $AAAAA$
• $EFFFF$
• $GFFFF$
• $1234567890ABCDEF$

5. Convertire dalla base 2 alla base 10 i seguenti numeri espressi in codifica naturale?

• $0$
• $1$
• $10$
• $11$
• $100$
• $1000$
• $10000$
• $100000$
• $1000001$
• $100000000$
• $1010101$
• $1101011010$

6. Convertire dalla base 10 alla base 2 i seguenti numeri espressi in codifica naturale?

• $0$
• $1$
• $2$
• $4$
• $7$
• $8$
• $57$
• $127$
• $128$
• $257$

7. Calcolare il valore delle seguenti espressioni (i numeri sono espressi in codifica naturale in base 2):

• $0 + 1$
• $0 + 10$
• $101 + 1$
• $1111 + 1$
• $1010101 - 1$
• $111011 - 11$
• $110 - 10$
• $1101101 - 1101$

8. Calcolare il valore delle seguenti espressioni e fornire il risultato in base 2 (i numeri sono espressi in codifica naturale in base 10)?

• $2 * 2$
• $8 * 2$
• $17 * 4$
• $128 * 2$
• $128 * 8$
• $127 * 16$
• $256 * 4$
• $129 * 16$

9. Calcolare:

• $8\ mod\ 2$
• $9\ mod\ 2$
• $10\ mod\ 2$
• $0\ mod\ 2$
• $3\ mod\ 3$
• $4\ mod\ 3$
• $16\ mod\ 4$
• $17\ mod\ 4$
• $255\ mod\ 16$