Esercizio su codici bifissi
Mi è stato assegnato il seguente esercizio da risolvere:
Sull'esistenza di codici di questa forma non ci sono dubbi perché vale la disuguaglianza di Kraft-McMillan. Ho usato la seguente formula:
\(
\frac{1}{3}(1 + \frac{4}{3} + \frac{4}{9}) = \frac{25}{27} \leq 1
\)
Detto ciò, l'esercizio mi chiede di trovare un codice che gode delle seguenti proprietà:
1) E' bifisso.
2) Contiene parole di lunghezza progressiva, tra l'altro nel massimo numero possibile, perché se mi avesse chiesto 5 parole di lunghezza 2 o 5 parole di lunghezza 3, non sarebbe stato bifisso ("massimo" per il numero di lettere che ho nell'alfabeto).
3) Contiene un numero di parole di lunghezza unitaria minore della cardinalità dell'alfabeto. Se avessi avuto |A| parole di lunghezza unitaria, il codice sarebbe stato unico, ossia A stesso.
In effetti la scelta delle parole all'interno di un codice bifisso, che gode delle proprietà sopra elencate, è influenzata dalle parole di lunghezza unitaria fissate all'inizio. Quello che voglio provare è che fissata la lettera a, o la lettera b, o la lettera c, allora il codice che ne deriva è unico. Questo giustificherebbe sia il "quali" che il "quanti" della traccia, ossia:
\(
X_a = \{a, bb, bc, cb, cc, bab, bac, cab, cac\}\\
X_b = \{b, aa, ac, ca, cc, aba, abc, cba, cbc\}\\
X_c = \{c, aa, ab, ba, bb, aca, acb, bca, bcb\}
\)
E dunque i codici bifissi sono tre.
Ho provato a estendere un po' il ragionamento, per generalizzare, e mi sono reso conto che codici di questo tipo, senza considerare per forza un numero massimo di parole e non per forza una sola parola di lunghezza unitaria, hanno una forma ben precisa.
Provando a formalizzare:
\(
A := \{a_1, . . ., a_n\}, n \in \mathbb{N} \\
A' := \{a_{i_1}, . . ., a_{i_k}\}, k \in \mathbb{N}, 1 \leq k < n, i \in \{1, . . . , n\}
\)
Banalmente:
\(
A' \subset A
\)
Dove \( A \) è l'alfabeto e \(A'\) sono le parole di lunghezza unitaria che devono appartenere al codice che cerchiamo.
Denotato con \(X_{A'}\) il codice di proprietà sopra elencate, allora:
\(
X_{A'} = A' \cup (A - A')[\bigcup_{n \in \mathbb{N_0}} (A')^n](A -A')
\)
Sono abbastanza sicuro del ragionamento, anche se non sono riuscito a dimostrare l'uguaglianza ed è uno dei motivi per i quali scrivo.
Mi chiedevo anche se esistesse un modo per determinare il numero di codici a priori, senza doverli prima cercare. Nell'esercizio che mi è stato assegnato è chiaro che i codici sono 3 e sono quelli.
Ma c'è un modo per ricavare quel numero usando, non so, le distribuzioni di Bernoulli?
Spero di essermi spiegato bene, mi scuso per eventuali errori e ringrazio chiunque sia disposto ad aiutarmi.
Si consideri l'alfabeto A = {a, b, c}. Quanti e quali sono i codici bifissi su A costituiti da
9 parole, di cui 1 di lunghezza 1, 4 di lunghezza 2 e 4 di lunghezza 3?
Sull'esistenza di codici di questa forma non ci sono dubbi perché vale la disuguaglianza di Kraft-McMillan. Ho usato la seguente formula:
\(
\frac{1}{3}(1 + \frac{4}{3} + \frac{4}{9}) = \frac{25}{27} \leq 1
\)
Detto ciò, l'esercizio mi chiede di trovare un codice che gode delle seguenti proprietà:
1) E' bifisso.
2) Contiene parole di lunghezza progressiva, tra l'altro nel massimo numero possibile, perché se mi avesse chiesto 5 parole di lunghezza 2 o 5 parole di lunghezza 3, non sarebbe stato bifisso ("massimo" per il numero di lettere che ho nell'alfabeto).
3) Contiene un numero di parole di lunghezza unitaria minore della cardinalità dell'alfabeto. Se avessi avuto |A| parole di lunghezza unitaria, il codice sarebbe stato unico, ossia A stesso.
In effetti la scelta delle parole all'interno di un codice bifisso, che gode delle proprietà sopra elencate, è influenzata dalle parole di lunghezza unitaria fissate all'inizio. Quello che voglio provare è che fissata la lettera a, o la lettera b, o la lettera c, allora il codice che ne deriva è unico. Questo giustificherebbe sia il "quali" che il "quanti" della traccia, ossia:
\(
X_a = \{a, bb, bc, cb, cc, bab, bac, cab, cac\}\\
X_b = \{b, aa, ac, ca, cc, aba, abc, cba, cbc\}\\
X_c = \{c, aa, ab, ba, bb, aca, acb, bca, bcb\}
\)
E dunque i codici bifissi sono tre.
Ho provato a estendere un po' il ragionamento, per generalizzare, e mi sono reso conto che codici di questo tipo, senza considerare per forza un numero massimo di parole e non per forza una sola parola di lunghezza unitaria, hanno una forma ben precisa.
Provando a formalizzare:
\(
A := \{a_1, . . ., a_n\}, n \in \mathbb{N} \\
A' := \{a_{i_1}, . . ., a_{i_k}\}, k \in \mathbb{N}, 1 \leq k < n, i \in \{1, . . . , n\}
\)
Banalmente:
\(
A' \subset A
\)
Dove \( A \) è l'alfabeto e \(A'\) sono le parole di lunghezza unitaria che devono appartenere al codice che cerchiamo.
Denotato con \(X_{A'}\) il codice di proprietà sopra elencate, allora:
\(
X_{A'} = A' \cup (A - A')[\bigcup_{n \in \mathbb{N_0}} (A')^n](A -A')
\)
Sono abbastanza sicuro del ragionamento, anche se non sono riuscito a dimostrare l'uguaglianza ed è uno dei motivi per i quali scrivo.
Mi chiedevo anche se esistesse un modo per determinare il numero di codici a priori, senza doverli prima cercare. Nell'esercizio che mi è stato assegnato è chiaro che i codici sono 3 e sono quelli.
Ma c'è un modo per ricavare quel numero usando, non so, le distribuzioni di Bernoulli?
Spero di essermi spiegato bene, mi scuso per eventuali errori e ringrazio chiunque sia disposto ad aiutarmi.
Risposte
Cos'è un codice bifisso?
X è un codice bifisso se nessuna parola in X è un prefisso o suffisso di qualunque altra parola in X
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo