B1 · Episode 2 · 5:10
Ensuring Unique Decoding in Binary Codes
This episode explains how to eliminate ambiguity in binary coding by ensuring each symbol has a fixed-length code (e.g., 5 bits), so any encoded string decodes uniquely to one word. It demonstrates encoding/decoding steps and includes a classroom activity for practice.
Source：stph / aperi.tube · License：CC BY-SA 4.0
Transcript
Je vais fabriquer un mot qui ne veut rien dire,
I’m going to create a word that means nothing,
mais qui est valide du point de vue du décodage.
but one that is valid from a decoding perspective.
Et des mots comme ça.
Words like this.
Je peux en trouver beaucoup.
I can find many of them.
Par exemple, ici, FDACAD est aussi un
For example, here, FDACAD is also a
décodage valide de ce même code.
valid decoding of this same code.
Je prends d'abord 101, puis 11, puis 0, puis 10, etc.
I first take 101, then 11, then 0, then 10, and so on.
Je vous en ai mis encore deux autres, xax et coed,
I’ve listed two more: xax and coed,
qui sont des décodages valides de notre code.
which are both valid decodings of our code.
Alors là, on a un problème, c'est que suivant comment on décompose le code,
So here’s a problem: depending on how we split up the code,
on tombe sur des mots différents.
we end up with different words.
Autrement dit, à partir d'un code, on
In other words, from a single code,
peut retrouver plusieurs mots.
we can recover several different words.
Et nous ce qu'on voudrait, c'est ne pas avoir le choix.
What we actually want is no ambiguity.
On voudrait que un code égale un mot.
We want one code to equal exactly one word.
Alors, comment faire ça?
So, how do we achieve that?
D'abord, on va revenir sur nos codes et faire quelques constats.
First, let’s go back to our codes and make some observations.
On peut constater que le code de la lettre C, c'est
We can observe that the code for letter C is
le même que le code du mot BA.
the same as the code for the word BA.
Une conséquence de ça, c'est que n'importe quel mot qui commence par BA,
One consequence is that any word beginning with BA,
si je remplace par C, je trouve le même code.
if we replace BA with C, yields the same code.
Et ça marche dans l'autre sens, n'importe quel mot qui commence par C,
And it works the other way too: any word beginning with C,
si je remplace C par BA,
if we replace C with BA,
je vais fabriquer le même code.
will produce the same code.
Et donc ça va nous générer des problèmes.
And so, this will cause problems.
Je peux trouver d'autres exemples, par exemple le code de F,
I can find other examples, such as the code for F,
c'est le même que le code de CB.
it’s the same as the code for CB.
Des exemples comme ça, il y en a beaucoup.
There are many such examples.
Le problème, c'est que.
The problem is that
Certains codes sont des morceaux d'autres codes.
some codes are substrings of other codes.
Le code de A, c'est un morceau du code de C.
the code for A is a substring of the code for C.
Le code de C, c'est un morceau du code de
The code for C is a substring of the code for
E, etc. Nous, on voudrait éviter ça.
E, and so on. We want to avoid this.
Eh bien, un moyen simple qu'on peut faire pour éviter ça,
Well, a simple way we can avoid this is
c'est de fabriquer des côtes qui ont tous la même taille.
to create codes that all have the same length.
Et pour faire ça, ce que je vous propose,
To do this, what I propose is
c'est d'ajouter des zéros devant les codes trop courts.
adding zeros in front of codes that are too short.
Alors voilà, je les ai ajoutés,
So here, I’ve added them,
je les ai mis en bleu pour que vous les voyez bien,
and highlighted them in blue so you can see them clearly,
mais ensuite ils seront en noir. En bleu,
but later they’ll be black. Using blue would be forbidden,
ce serait interdit parce que ça générerait un code ternaire avec des 0 bleus,
because it would generate a ternary code with blue 0s,
des 0 noirs et des 1.
black 0s, and 1s.
Nous, on a le droit uniquement aux 0 et aux 1.
We’re only allowed to use 0s and 1s.
Alors voilà, je vous ai mis nos nouveaux codes à gauche,
So here are our new codes on the left,
et maintenant on va recommencer l'encodage.
and now we’ll re-encode.
On repart du même mot.
We start again from the same word.
Cette fois- ci, le code de C, c'est
This time, the code for C is
0 0 0 1 0, le code de H, c'est 0 0 1
0 0 0 1 0; the code for H is 0 0 1 1 1;
1 1, le code de A, c'est
the code for A is
0 0 0 0 0, et le code de T, c'est.
0 0 0 0 0, and the code for T is.
1 0 0 1 1. Qu'est- ce que ça donne du point de vue du décodage?
1 0 0 1 1. What does this mean from the decoding perspective?
Je vous ai mis le code en haut.
I’ve written the code at the top.
Et bien maintenant, on n'a plus le choix.
Well now, we have no choice.
On fait des groupes de cinq chiffres.
We group the digits into sets of five.
D'abord 0 0 0 1 1.
First: 0 0 0 1 1.
Puis les cinq suivants, puis les cinq suivants, puis les cinq suivants,
Then the next five digits, then the next five, then the next five,
et à partir de ces codes, on retrouve les lettres, d'abord le C,
and from these codes, we recover the letters—first C,
puis le H, puis le A,
then H, then A,
puis le T. Et voilà, on a réussi.
then T. And there you go—we’ve succeeded!
On a utilisé uniquement des 0 et des 1, et
We used only 0s and 1s,
on a bien la propriété qu'un code égale un mot.
and we’ve achieved the property that each code corresponds to exactly one word.
Ce que je vous propose pour terminer,
To wrap up, I’d like you to do a little hands-on activity.
c'est maintenant que ce soit à vous de travailler un petit peu.
Now it’s your turn to practice a bit.
Alors vous allez sortir vos ardoises et vous allez faire la chose suivante.
So take out your mini whiteboards and do the following.
Vous allez écrire un petit mot sur votre ardoise.
Write a short word on your whiteboard.
Petit, c'est quatre ou cinq lettres mais pas plus, sinon le code sera trop grand.
‘Short’ means four or five letters—no more, otherwise the code will get too long.
Et vous allez essayer de l'écrire pour que votre voisin ne le voit pas.
Try to write it so your neighbor can’t see it.
Moi, par exemple, j'écris moto, mais c'est un secret.
For example, I’m writing ‘moto’—but that’s a secret!
Ensuite, vous allez fabriquer le code de votre mot.
Next, create the code for your word.
Donc vous voyez, pour M, j'ai écrit le code, puis pour O, puis pour T,
So you see—I’ve written M’s code, then O’s, then T’s,
puis pour O. Ensuite, je vais effacer le mot que j'ai écrit.
and finally the second O’s. Then I’ll erase the original word.
Et je garde uniquement le code.
I’ll keep only the code.
Et ensuite, je vais échanger mon ardoise avec celle de mon voisin.
Then I’ll swap my whiteboard with my neighbor’s.
Voilà, je récupère une nouvelle ardoise avec un code que je ne connais pas.
There—now I’ve got a new whiteboard with a code I don’t know.
Eh bien, je vais essayer de le décoder.
Well, I’ll try to decode it!
Alors pour ce faire, je vais faire des groupes de cinq chiffres.
To do this, I’ll group the digits into sets of five.
Et ensuite, je vais regarder dans mon tableau
Then, I’ll look at my reference table,
les codes à quelle lettre ils correspondent.
to see which letter each code stands for.
Donc le premier correspond à la lettre F,
So the first one corresponds to the letter F,
puis la lettre I, puis la lettre N, puis la lettre I.
then the letter I, then N, then I.
Et voilà, c'est fini.
And there you go—it’s done!
Si vous avez une question, je vous ai mis mon adresse mail, n'hésitez pas.
If you have any questions, feel free to email me—I’ve shared my address.
Et puis je vous laisse les codes pour que vous puissiez travailler.
Also, I’ve provided the codes for you to practice with.
Bonne journée, merci.
Have a great day—thank you!