Fonctions booléennes

Les opérations ensemblistes

Proposition. Étant donné un ensemble fini $X$ à $n$ éléments, et une énumération $x_1,\dots ,x_n$ des éléments de $x$, la fonction :

$$>b_1\cdots b_n\mapsto \{x_i\mid b_i=1\}>$$

définit une bijection de ${\mathbf{B}}^n$ dans $\mathcal{P}(X)$.

En utilisant l’isomorphisme de la proposition, qui établit une bijection entre les mots binaires de longueur $n$ et les sous-ensembles d’un ensemble $X$ à $n$ éléments, les correspondances entre les opérations booléennes et les opérations ensemblistes sont:

1. Négation $\mathrm{\neg }$ : complémentaire d’un sous-ensemble $S\subseteq X$, noté $S^c$. $\mathrm{\neg }S\equiv X\setminus S$.

2. Conjonction $\wedge$ : l’intersection de deux sous-ensembles $S$ et $T$. $S\wedge T\equiv S\cap T$.

3. Disjonction $\vee$ : l’union de deux sous-ensembles $S$ et $T$. $S\vee T\equiv S\cup T$.

4. Implication ($\Rightarrow$) : l’union du complémentaire de $S$ avec $T$.
   $S\Rightarrow T\equiv S^c\cup T$.

5. Équivalence ($\iff$) : l’union des parties où $S$ et $T$ ont les mêmes éléments (soit tous deux présents, soit tous deux absents).
   $S\iff T\equiv (S\cap T)\cup (S^c\cap T^c)$.

6. Disjonction exclusive ($\oplus$) : la différence symétrique entre $S$ et $T$, qui regroupe les éléments présents dans un seul des deux ensembles, mais pas dans les deux simultanément.
   $S\oplus T\equiv (S\setminus T)\cup (T\setminus S)$.

Fonctions bouléennes

Nombre d’opérations booléennes $n$-aires et de fonctions ${\mathbf{B}}^n\to {\mathbf{B}}^k$

1. Nombre d’opérations booléennes $n$-aires : Une opération booléenne $n$-aire est une fonction ${\mathbf{B}}^n\to \mathbf{B}$, où $\mathbf{B}=\{0,1\}$ est l’ensemble des valeurs booléennes. Le nombre total de telles fonctions est donné par le nombre d’assignations possibles de valeurs de vérité pour $2^n$ entrées (les $2^n$ combinaisons des $n$ variables booléennes) vers $\{0,1\}$. Il y a donc $2^{2^n}$ fonctions booléennes $n$-aires.
2. Une fonction de ${\mathbf{B}}^n$ vers ${\mathbf{B}}^k$ associe à chaque entrée de ${\mathbf{B}}^n$ une sortie dans ${\mathbf{B}}^k$. Ce qui équivaut à décrire $k$ fonctions indépendantes ${\mathbf{B}}^n\to \mathbf{B}$. Le nombre total de telles fonctions est alors $(2^k{)}^{2^n}=2^{k\cdot 2^n}$.

Écriture de toute opération booléenne en termes des constantes 0, 1, $\mathrm{\neg }$, $\wedge$, et $\vee$

Preuve : Montrons que toute opération booléenne peut être exprimée en utilisant $\mathrm{\neg }$, $\wedge$, $\vee$, et les constantes $0$ et $1$, grâce à la DNF.

On sait que toute fonction booléenne $f$ est entièrement caractérisée par sa table de vérité, qui énumère toutes les combinaisons possibles des $n$ variables booléennes et leur valeur de sortie.

1. Pour chaque combinaison $(b_1,\dots ,b_n)$ où $f(b_1,\dots ,b_n)=1$, on construit un minterme :

   $$m=\underset{i=1}{\overset{n}{\bigwedge }}(b_i\text{ ou }\mathrm{\neg }{b}_i),$$

   où chaque $b_i$ est pris tel qu’il correspond à la valeur de la variable dans cette ligne de la table.

2. La fonction $f$ est exprimée comme une disjonction de ces mintermes :

   $$f(x_1,\dots ,x_n)=\underset{m\in \text{Mintermes}}{\bigvee }m.$$

   Les constantes $0$ et $1$ représentent les cas triviaux où $f=0$ (fonction nulle, aucun minterme) ou $f=1$ (fonction toujours vraie).

Le $\wedge$ $2^p$-aire en utilisant $2^p-1$ fois le $\wedge$ binaire

L’opération $\wedge$ $n$-aire correspond à une conjonction logique sur $n$ entrées. On suppose $n=2^p$ pour un entier $p\ge 0$. Une manière naturelle de construire cette opération est d’appliquer récursivement le $\wedge$ binaire suivant une structure en arbre binaire :

Diviser les $2^p$ entrées en paires successives, appliquant $\wedge$ à chaque paire (ce qui nécessite $2^{p-1}$ applications). Répéter ce processus sur les $2^{p-1}$ résultats intermédiaires (ce qui prend $2^{p-2}$ applications en plus), et ainsi de suite, jusqu’à ce qu’il reste une seule valeur.

Le nombre total d’applications nécessaires est donc la somme des termes d’une progression géométrique :

$S=2^{p-1}+2^{p-2}+\cdots +1=\frac{2^p-1}{2-1}=2^p-1.$

Peut-on faire mieux ?

Si $k<2^p-1$, alors il reste plus d’une sortie à produire, car $2^p-k>1$. Le résultat final (le $\wedge$ $n$-aire) ne peut pas dépendre de toutes les $2^p$ entrées, ce qui est contradictoire car par définition, l’opération $\wedge$ $n$-aire doit renvoyer 1 si toutes les entrées valent 1, et 0 sinon. Pour assurer ça, il faut que chaque entrée initiale contribue, directement ou indirectement, au résultat final.

Codages binaires de longueur fixée

Quelques Définitions

1. $A^n$ l’ensemble des mots de longueur fixe $n$ sur l’alphabet $A$ :

   $$A^n=\{u=a_1{a}_2\cdots a_n|a_i\in A,\mathrm{\forall }i\in \{1,2,\dots ,n\}\}.$$

   Par exemple si $A=\{0,1\}$ et $n=2$, alors $A^2=\{00,01,10,11\}$.

   $A^n$ est utile pour représenter des messages ou codes de taille fixée, par exemple dans les codages à longueur fixe.

2. $A^{\ast }$ est l’ensemble des mots de longueur arbitraire (y compris nulle) sur l’alphabet $A$ :

   $$A^{\ast }=\bigcup _{n\ge 0}{A}^n.$$

   Ce qui inclut:

   • Les mots de longueur $0$, c’est-à-dire l’ensemble $\{\epsilon \}$ où $\epsilon$ est le mot vide.
   • Les mots de longueur $1$ ( simplement $A$).
   • Les mots de longueur $n$ pour tout $n\ge 2$.

   Par exemple : si $A=\{a,b\}$, alors $A^{\ast }=\{\epsilon ,a,b,aa,ab,ba,bb,aaa,\dots \}$.

   $A^{\ast }$ est plus général et utilisé pour représenter des messages de longueur variable, comme dans les codages préfixes.

3. Soit $X$ un ensemble fini. Une convention de codage sur $n$ bits des éléments de $X$ est définie par:

   • une fonction de codage $\gamma :X\to {\mathbf{B}}^n$, et
   • une fonction partielle de décodage $\delta :{\mathbf{B}}^n\rightharpoonup X$, telles que :
   $$\delta (\gamma (x))=x\text{ pour tout }x\in X$$

   Un code de $x\in X$ selon $\delta$ est n’importe quelle préimage $u\in {\mathbf{B}}^n$ telle que $\delta (u)=x$. La fonction $\gamma$ sélectionne un de ces codes.

   • $\delta$ o $\gamma$ est l’identité sur $X$, deux éléments distincts de $X$ ne peuvent avoir la même image par $\gamma$. Ce qui impose que $\gamma$ est injective.

     • $\gamma$ n’est pas nécessairement surjective. Certains mots binaires de ${\mathbf{B}}^n$ peuvent ne pas correspondre au codage d’un élément de $X$.

   • Tout élément de $X$ possède au moins un code, donc $\delta$ est surjective.

     • $\delta$ n’est pas toujours totalement définie. Il peut exister des mots binaires dans ${\mathbf{B}}^n$ qui ne décodent aucun élément de $X$.
     • Un même élément de $X$ peut être associé à plusieurs mots binaires par $\delta$. La correspondance n’est donc pas forcément univoque pour la fonction de décodage.

À quelle condition un ensemble $X$ peut-il admettre un codage sur $n$ bits ?

Un ensemble $X$ peut admettre un codage sur $n$ bits si et seulement si le nombre d’éléments de $X$ satisfait :

$|X|\le 2^n$.

En effet, un mot binaire de longueur $n$ peut représenter $2^n$ valeurs distinctes (toutes les combinaisons possibles des $n$ bits). Si $|X|>2^n$, il est impossible d’associer un mot binaire unique à chaque élément de $X$.

Dès que $X$ est non vide, toute convention de codage peut être étendue pour que la fonction de décodage soit totale.

Une fonction de décodage $\delta$ est dite totale si elle est définie pour tous les mots binaires possibles de longueur $n$ (tous les éléments de $B^n$)

Si $X\ne \mathrm{\varnothing }$, on peut compléter toute fonction de décodage partielle $\delta$ comme suit : Pour tout mot $u\in B^n$ qui n’est pas déjà associé à un élément de $X$ par $\delta$, on choisit arbitrairement un élément $x\in X$ et on pose $\delta (u)=x$. Ainsi, $\delta$ devient définie sur tout $B^n$.

Cette redondance ne doit pas poser pas problème dans les situations où on ne demande pas d’unicité : par exemple, si l’on veut juste une correspondance valide pour décoder n’importe quel mot binaire vers un élément de $X$, l’unicité n’est pas nécessaire.

• La fonction de codage $\gamma :X\to B^n$ reste injective (chaque élément de $X$ a un code unique).

Par exemple l’objectif peut être de garantir un décodage, même arbitraire, dans tous les cas possibles (comme dans certains systèmes d’encodage où le “reste des cas” mènent à une valeur “par défaut”).

• Le problème de duplication ne survient qu’au moment de définir une fonction de décodage totale $\delta :B^n\to X$, qui ajoute des correspondances pour les mots binaires inutilisés.

À quelle condition un ensemble $X$ peut-il admettre un codage sur $n$ bits, avec une fonction de codage surjective (ou, de manière équivalente, une fonction de décodage totale et injective) ?

Une condition nécessaire est suffisante :

En effet, ($\text{1}$) est nécessaire: $B^n$ contient exactement $2^n$ mots binaires distincts. Si $\gamma :X\to B^n$ est injective, alors $|X|\le |B^n|=2^n$, car un élément de $X$ ne peut pas partager un code avec un autre. Si $\delta :B^n\to X$ est injective et totale, chaque mot binaire de $B^n$ doit correspondre à un élément unique de $X$. Donc, $|X|\ge 2^n$. En combinant $|X|\le 2^n$ et $|X|\ge 2^n$, on déduit que $|X|=2^n$.

($\text{1}$) est suffisante aussi : supposons $|X|=2^n$. Construisons une fonction $\gamma :X\to B^n$ injective : comme $|X|=|B^n|$, $\gamma$ est bijective, une telle bijection existe (par définition de la bijection). Construisons $\delta :B^n\to X$ comme l’inverse de $\gamma$ (car $\gamma$ est bijective).

• $\delta$ est injective car chaque code est associé à un unique élément de $X$ par ${\gamma }^{-1}$.
• $\delta$ est totale car tout mot binaire dans $B^n$ a une préimage dans $X$.

Un codage sur $n$ bits avec une fonction de décodage injective et totale existe si et seulement si $|X|=2^n$.

Addition dans $\mathbb{Z}/4\mathbb{Z}$

En identifiant ${\mathrm{B}}^4$ avec ${\mathrm{B}}^2\times {\mathrm{B}}^2$, on peut voir toute fonction ${\mathrm{B}}^4\to {\mathrm{B}}^2$ comme une opération binaire sur $\mathrm{Z}/2^2\mathrm{Z}=\mathrm{Z}/4\mathrm{Z}$, modulo codage (disons petit-boutiste).

Vérifions que la fonction

représente l’addition : ${\delta }_2((b_0\wedge c_0)\oplus b_1\oplus c_1,b_0\oplus c_0)={\delta }_2\left(b_1{b}_0\right)+{\delta }_2\left(c_1{c}_0\right)mod4$ avec ${\delta }_2$ le décodage binaire vers un entier dans $\mathbb{Z}/4\mathbb{Z}$.

On a :

• ${\delta }_2(b_1{b}_0)=2b_1+b_0$,
• ${\delta }_2(c_1{c}_0)=2c_1+c_0$.

La somme est donc :

La retenue entre $b_0$ et $c_0$ est donnée par $b_0\wedge c_0$. La somme des bits de poids faible modulo $2$ est (gère la somme des unités):

La somme des bits de poids fort inclut la retenue $b_0\wedge c_0$ (gère la somme des bits “plus significatifs”, en tenant compte des retenues depuis les bits faibles.):

Ce qui correspond exactement à $(b_0\wedge c_0)\oplus b_1\oplus c_1$.

Donc la concaténation de ces deux résultats donne bien:

$((b_0\wedge c_0)\oplus b_1\oplus c_1)(b_0\oplus c_0)$

Donc, la fonction donnée calcule :

Exemple:

Dans $\mathbb{Z}/4\mathbb{Z}$, chaque entier est représenté par 2 bits : $3\mapsto 11$.

Additionnons : $$ \begin{array}{r@{}r@{}r@{}r} & ^1 & ^1 & \ & & 1 & 1\

• & & 1 & 1 \ \hline & 1 & 1 & 0 \ \end{array} $$

Ce qui donne $6$ en base de $10$. Avec la troncation pour correspondre a $\mathbb{Z}/4\mathbb{Z}$ , où uniquement les deux derniers bits comptent, on devrait avoir une représentation binaire de $10$, qui représente $2$ en base de 10 et dans

, donc on a bien $6\equiv 2\text{mod}4$.

• Les bits de poids faible sont les derniers bits (les plus à droite) :

  • Bit faible de $3$: $b_0=1$,

  En faisant l’addition modulo $2$ (XOR, $\oplus$) :

  $$b_0\oplus c_0=1\oplus 1=0.$$

  Or, comme $1+1=10$ en binaire, une retenue est générée :

  $$b_0\wedge c_0=1\wedge 1=1.$$

• Les bits de poids fort sont les premiers bits (les plus à gauche) :

  • Bit fort de $3$: $b_1=1$,

  Nous ajoutons les bits forts, en tenant compte de la retenue générée par les bits faibles :

  $$(b_0\wedge c_0)\oplus b_1\oplus c_1=1\oplus 1\oplus 1=1$$

  La concaténation des deux résultats donne :

  $((b_0\wedge c_0)\oplus b_1\oplus c_1)(b_0\oplus c_0)=10$

Données séquentielles

Le monoïde des mots

3.1.8. Exercice (Généralités sur le monoïde des mots).

Non-commutativité du monoïde $A^{\ast }$ pour $|A|\ge 2$

Un mot $u\in A^{\ast }$ est une suite finie de symboles pris dans l’alphabet $A$. La concaténation de deux mots $u,v\in A^{\ast }$ est définie par :

où $u=u_1{u}_2\dots u_m$ et $v=v_1{v}_2\dots v_n$. Considérons un alphabet $A=\{a,b\}$. Prenons les mots $u=a$ et $v=b$. Alors :

Comme $ab\ne ba$, la concaténation n’est pas commutative. Donc, $A^{\ast }$ est non-commutatif dès que $A$ contient au moins deux éléments.

Morphisme de monoïdes de $A^{\ast }$ vers $\mathbb{N}$

La longueur d’un mot $u=u_1{u}_2\dots u_n\in A^{\ast }$ est donnée par $|u|=n$. Vérifions que la fonction $f:A^{\ast }\to \mathbb{N}$, définie par $f(u)=|u|$, est un morphisme de monoïdes:

1. Elément neutre : l’élément neutre de $A^{\ast }$ est le mot vide $\epsilon$. Par définition, $|\epsilon |=0$, qui est l’élément neutre de $(\mathbb{N},+)$.

2. Opération : pour $u,v\in A^{\ast }$, on a $|u\cdot v|=|u|+|v|$. Donc, $f(u\cdot v)=$ $f(u)+f(v)$, ce qui prouve que $f$ est un morphisme.

   Si $A=\{a\}$, chaque mot $u\in A^{\ast }$ est de la forme $a^n$ pour $n\in$ $\mathbb{N}$. La longueur $|u|$ est une bijection entre $A^{\ast }$ et $\mathbb{N}$. Dans ce cas, $f$ est un isomorphisme. Si $A$ contient plusieurs symboles, il existe des mots distincts de même longueur (par exemple, $ab$ et $ba$ pour $A=\{a,b\}$ et $|ab|=|ba|=2$ ). Donc, $f$ n’est pas injective et donc pas un isomorphisme.

Dénombrabilité de $A^{\ast }$

1. Si $A$ est fini ou dénombrable, $A^{\ast }=\bigcup _{n\in \mathbb{N}}{A}^n$, où $A^n$ est l’ensemble des mots de longueur $n$. Chaque $A^n$ est une puissance cartésienne de $A$, et un ensemble dénombrable de mots de longueur finie est une union dénombrable d’ensembles dénombrables, donc dénombrable.
2. Si $A$ est non dénombrable, $A^{\ast }$ contient les mots de longueur 1 ( $A^1=A$ ), qui forment déjà un ensemble non dénombrable. donc, $A^{\ast }$ n’est pas dénombrable.

Donc, $A^{\ast }$ est dénombrable si et seulement si $A$ est dénombrable.

Programmes élémentaires

fonction gonfle(s:str,k:int)

def gonfle(s: str, k: int) -> str:
    #Retourne une chaîne où chaque caractère de "s" est répété "k" fois.
    return "".join(char * k for char in s)

print(gonfle("ab", 3))  # Résultat : "aaabbb"

1. Join est utilisée pour construire une nouvelle chaine en concaténant les répétitions de chaque caractère.
2. char $\ast k$ génère $k$ copies pour chaque caractère.

On peut aussi faire à la main:

def gonfle(s,k):
    retour = ""
    for c in s:
        for i in range(k):
            retour = retour+c
    return retour

ou bien comme k*c retourne la concaténation de $k$ copie du charactère c :

def gonfle(s,k):
    retour = ""
    for c in s:
        retour = retour + k*c
    return retour

fonction palindrome(u)

def palindrome(u) -> bool:
    return u == u[::-1]
print(palindrome("radar"))  # Résultat : True
print(palindrome("python"))  # Résultat : False

1. L’expression $u[::-1]$ retourne le mot $u$ renversé.
2. La comparaison $u==u[::-1]$ vérifie si le mot est identique à son inverse.

On peut faire aussi à la main:

def palindrome(u):
    l = len(u)
    for i in range(1//2):
        If u[i] != u[l-i-1]:
        	return False
	return True

ou alors:

def palindrome(u):
    return all(u[i] == u[-i-1] for i in range(len(u)))

ou bien en utilisant la fonction reversed (la conversion en tuple des deux côtés de l’égalité est nécessaire pour obtenir des séquences du même type) :

def palindrome(u):
    return tuple(reversed(u)) == tuple(u)

mais c’est moins efficace parce qu’on fait deux fois plus de tests (on parcourt toute la liste) ; ou bien avec un usage astucieux des tranches. :

def palindrome(u):
    l = len(u)
    return u[:1//2] == u[:-1-1//2:-1]

Codes de longueurs variables

Codages préfixes

Dans la théorie du codage et la représentation des données, les codages préfixes garantissent que les séquences de symboles encodés peuvent être décodées de manière unique. La propriété préfixe assure qu’aucun mot de code n’est le préfixe d’un autre, ce qui permet un décodage sans ambiguïté des codes concaténés. Cette propriété est utilisée dans des applications comme la compression de données (par exemple, le codage de Huffman) ou les encodages de caractères (comme UTF-8).

Soit $\gamma :X\to A^{\ast }$ une fonction de codage, où $X$ est un ensemble fini et $A^{\ast }$ l’ensemble des mots finis sur un alphabet $A$. On dit que $\gamma$ est un codage préfixe si, pour tous $x,y\in X$, $\gamma (x)$ est un préfixe de $\gamma (y)$ si et seulement si $x=y$.

Vérification de l’injectivité de ${\gamma }^{\ast }$ :

Soient $x_1,x_2,\dots .,x_n\in X$ et désignons $u=x_1{x}_2\dots .x_n\in X^{\ast }$.

Définissons ${\gamma }^{\ast }$ le morphisme : ${\gamma }^{\ast }(x_1{x}_2\dots x_n)=\gamma (x_1)\gamma (x_2)\dots \gamma (x_n)$.

Si $\gamma$ est un codage préfixe sur $X$, aucun code $\gamma (x)$ n’est un préfixe strict d’un autre code $\gamma (y)$, sauf si $x=y$.

• Si $u=\epsilon$ alors ${\gamma }^{\ast }(u)={\gamma }^{\ast }(\epsilon )=\gamma (\epsilon )=\epsilon \in A$. Si ${\gamma }^{\ast }(v)={\gamma }^{\ast }(u)=\epsilon$, alors $v=u=\epsilon$ également.

• Supposons que deux mots $u=x_1{x}_2\cdots x_k$ et $v=y_1{y}_2\cdots y_m$ de $X^{\ast }$ sont tels que ${\gamma }^{\ast }(u)={\gamma }^{\ast }(v)$. Donc :

  $$\gamma (x_1)\gamma (x_2)\cdots \gamma (x_k)=\gamma (y_1)\gamma (y_2)\cdots \gamma (y_m).$$

  Comme $\gamma$ est un codage préfixe, aucun code $\gamma (x)$ ne peut être un préfixe strict d’un autre code $\gamma (y)$. donc ça garantit que le début de ${\gamma }^{\ast }(u)$, c’est-à-dire $\gamma (x_1)$, correspond nécessairement au début de ${\gamma }^{\ast }(v)$, soit $\gamma (y_1)$ et vice versa. Par conséquent, on a :

  $$\gamma (x_1)=\gamma (y_1).$$

  Puisque $\gamma$ est injectif, ça implique que:

  $$x_1=y_1.$$

  En supprimant la première lettre, on obtient deux nouveaux mots :

  $$u^{\prime }=x_2{x}_3\cdots x_k,v^{\prime }=y_2{y}_3\cdots y_m.$$

  Comme $\gamma (x_1)=\gamma (y_1)$, il reste :

  $${\gamma }^{\ast }(u^{\prime })={\gamma }^{\ast }(v^{\prime }).$$

  Et ainsi de suite, par récurrence, on obtient $u=v$.

Codage de taille fixe est toujours un codage préfixe

Un codage de taille fixe $\gamma :X\to A^n$ associe à chaque élément de $X$ un mot de longueur constante $n$. Si deux codes distincts $\gamma (x)$ et $\gamma (y)$ ont toujours la même longueur, aucun ne peut être le préfixe de l’autre. Par conséquent, tout codage de taille fixe est nécessairement un codage préfixe.

Fonction prefixe(u, v) :

Voici une implémentation en Python d’une fonction qui retourne True si le mot u est préfixe de v et False sinon.

def prefixe(u, v):
    return v.startswith(u)

Avec les deux versions qui suivent on accepte que des mots de types différents soient préfixe l’un de l’autre ou non prefixe("a", ["a", "b"]) == True mais pas avec les autres versions (parce que pour Python une chaîne n’est jamais égale à une liste).

def prefixe(u,v):
    l = len(u)
    If l>len(v):
        return False
    for i in range(1):
        If u[1] != v[1]:
            return False
    return True

def prefixe(u,v):
    return len(u) <= len(v) and all(u[i] == v[i] for i in range(len(u)))


def prefixe(u,v):
    return len(u) <= len(v) and u == v[:len(u)]

UTF-8 est un codage préfixe

Chaque caractère unicode est codé par une séquence de 1 à 4 octets, où la structure du premier octet détermine la longueur totale de la séquence :

• 1 octet : $0xxxxxxx$ (ASCII, où $x$ représente des bits).
• 2 octets : $110xxxxx10xxxxxx$.
• 3 octets : $1110xxxx10xxxxxx10xxxxxx$.
• 4 octets : $11110xxx10xxxxxx10xxxxxx10xxxxxx$.

Tous les octets non initiaux commencent par $10$, ce qui les distingue des octets initiaux. Aucune séquence UTF-8 complète ne peut être un préfixe strict d’une autre séquence :

Les séquences à 1 octet ($0xxxxxxx$) ne peuvent jamais être le début d’une séquence à plusieurs octets, car les séquences à plusieurs octets commencent par $110$, $1110$, ou $11110$.

Les octets internes ($10xxxxxx$) ne peuvent pas être interprétés comme des séquences valides par eux-mêmes.

Par exemple, le code UTF-8 pour un caractère ASCII est $0xxxxxxx$. Ce code ne peut être le début d’une séquence UTF-8 valide à plusieurs octets, car un tel code doit commencer par $110$, $1110$, ou $11110$. D’où, UTF-8 est un codage préfixe.

Aucun suffixe strict n’est un préfixe

Un suffixe strict d’un code UTF-8 est une partie terminale d’un code, ne contenant pas son premier octet. Les suffixes stricts contiennent uniquement des octets non initiaux, qui ont la forme $10xxxxxx$.

Les octets non initiaux ($10xxxxxx$) ne peuvent pas être des octets initiaux (ils ne commencent ni par $0$, ni par $110$, $1110$, ou $11110$). Ils ne peuvent donc pas former un préfixe valide d’un autre code UTF-8, car un préfixe doit inclure le premier octet d’une séquence UTF-8.

Représenter les nombres

Théorème (Existence et unicité de l’écriture en base $B$ ).

Si on fixe $B>1$, alors tout entier $n\in [[B^k]]$

admet une unique écriture sous la forme

$$>n=\sum _{i=0}^{k-1}{c}_i{B}^i>$$

avec $0 \leq c_i

Démonstration:

• Existence:

  Cas de base $(k=0)$ : Si $k=0$, alors $n=0$, et l’écriture est immédiate. Étape de récurrence : Supposons que le théorème soit vrai pour $k-1$. Pour $k>0$, considérons comment $n$ peut être décomposé :

  $$n=\left(\sum _{i=0}^{k-2}{c}_{i+1}{B}^i\right)\times B+c_0$$

  Ici :

  • $c_0$ est le reste de la division euclidienne de $n$ par $B$ (le chiffre des unités).
  • La partie restante, $\sum _{i=0}^{k-2}{c}_{i+1}{B}^i$, est le quotient $n÷B$ écrit en base $B$ avec $k-1$ termes.

Par récurrence, l’existence et l’unicité de l’écriture du quotient garantissent celles de $n$.

• Unicité :

  Les coefficients $c_i$ sont déterminés par le processus de division euclidienne:

  • $c_0$ est le reste obtenu en divisant $n$ par $B$.
  • Les coefficients suivants proviennent des divisions successives du quotient par $B$.

Écriture en base 𝐵 en Python

Exemple d’une fonction representation(n,B)​ qui renvoie la liste des $c_i$, pour $0\le i<$ $|n{|}_B$ , et sa fonction réciproque valeur( c, B) qui calcule la somme étant donnée la liste c des coefficients et la base B .

def representation(n, B, k=None):
    """
    n (int): Le nombre entier à convertir.
    B (int): La base dans laquelle effectuer la conversion.
    en option : k (int): Longueur de l'écriture si spécifiée.
    """
    if n == 0:
        res = [0]
    else:
        res = []
        while n > 0:
            res.append(n % B)
            n //= B
        res.reverse()

    if k is None:
        return res
    elif k >= len(res):
        #Retourne: list[int]: Liste des chiffres de n en base B.
        return [0] * (k - len(res)) + res
    else:
        #Si k est fourni et est inférieur à la taille minimale.
        raise ValueError("La longueur k est inférieure à la taille minimale |n|_B.")

def valeur(c, B):
    # Retourne: int: La valeur entière.
    return sum(d * (B ** i) for i, d in enumerate(reversed(c)))

def conversion(c, B1, B2):
    """
    Convertit une écriture d'une base B1 à une base B2.
    c (list[int]): Liste des chiffres en base B1.
    """
    n = valeur(c, B1)
    #Retourne:list[int]: Liste des chiffres en base B2.
    return representation(n, B2)