Codage et décodage

Merci !

Annales corrigées
Classe(s) : Tle S | Thème(s) : Arithmétique
Type : Exercice | Année : 2013 | Académie : Antilles, Guyane
 
Unit 1 - | Corpus Sujets - 1 Sujet
 
Codage et décodage
 
 

Arithmétique

matT_1309_04_05C

ENS. DE SPÉCIALITÉ

39

CORRIGE

 

Antilles, Guyane • Septembre 2013

Exercice 4 • 5 points

Partie A

On considère l’algorithme suivant :

 

A et X sont des nombres entiers

Saisir un entier positif A

Affecter à X la valeur de A

Tant que X supérieur ou égal à 26

Affecter à X la valeur X– 26

Fin du tant que

Afficher X

 

>1. Qu’affiche cet algorithme quand on saisit le nombre 3 ?

>2. Qu’affiche cet algorithme quand on saisit le nombre 55 ?

>3. Pour un nombre entier saisi quelconque, que représente le résultat fourni par cet algorithme ?

Partie B

On veut coder un bloc de deux lettres selon la procédure suivante (détaillée en quatre étapes) :

  • Étape 1 : chaque lettre du bloc est remplacée par un entier en utilisant le tableau ci-dessous :
 

A

B

C

D

E

F

G

H

I

J

K

L

M

0

1

2

3

4

5

6

7

8

9

10

11

12

 
 

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

13

14

15

16

17

18

19

20

21

22

23

24

25

 

On obtient une matrice colonne x1 correspond à la première lettre du mot et x2 correspond à la deuxième lettre du mot.

  • Étape 2 : est transformé en tel que

.

La matrice est appelée la matrice de codage.

  • Étape 3 : est transformé en tel que

  • Étape 4 : est transformé en bloc de deux lettres en utilisant le tableau de correspondance donné dans l’étape 1.

Exemple :

Le bloc RE est donc codé en DP

>1. Justifier le passage de à puis .

>2. Soient x1, x2, , , quatre nombres entiers compris entre 0 et 25 tels que et sont transformés lors du procédé de codage en .

a) Montrer que .

b) En déduire que et puis que et .

>3. On souhaite trouver une méthode de décodage pour le bloc DP.

a) Vérifier que la matrice est la matrice inverse de C.

b) Calculer  tels que .

c) Calculer  tels que .

d) Quel procédé général de décodage peut-on conjecturer ?

>4. Dans cette question nous allons généraliser ce procédé de décodage.

On considère un bloc de deux lettres et on appelle z1 et z2 les deux entiers compris entre 0 et 25 associés à ces lettres à l’étape 3. On cherche à trouver deux entiers x1 et x2 compris entre 0 et 25 qui donnent la matrice  par les étapes 2 et 3 du procédé de codage.

Soient  et  tels que  où .

Soient x1 et x2, les nombres entiers tels que :



Montrer que .

Conclure.

>5. Décoder QC.

Durée conseillée : 60 min

Les thèmes clés

Algorithme • Produit matriciel • Congruences.

Nos coups de pouce

Partie B

>2. a) Appliquez les étapes 2 et 3 de la procédure à la matrice colonne et à la matrice colonne . Concluez en utilisant le fait que ces deux matrices sont transformées toutes les deux en la matrice colonne .

>3. a) Effectuez le produit matriciel . Concluez.

>5. Utilisez le procédé général de décodage établi à la question 3.

Corrigé

Partie A

>1. Analyse d’un algorithme et affichage en sortie au vu de l’entrée proposée

Si on saisit la valeur 3, X reçoit 3. Comme X n’est pas supérieur ou égal à 26, la condition de la boucle Tant que n’est pas vérifiée, cette dernière ne s’exécute donc pas et X s’affiche. Ainsi, cet algorithme affiche 3.

>2. Analyse d’un algorithme et affichage en sortie au vu de l’entrée proposée

Si on saisit la valeur 55, X reçoit 55. Comme X est supérieur ou égal à 26, la boucle Tant que s’exécute. X prend alors successivement les valeurs et . Dans ce dernier cas, X n’est pas supérieur ou égal à 26, la condition de la boucle Tant que n’est plus vérifiée, cette dernière s’arrête et X s’affiche. Cet algorithme affiche donc 3.

>3. Analyse générale d’un algorithme

Pour un nombre entier naturel saisi, cet algorithme affiche le reste de la division de par 26.

Partie B

>1. Étapes d’un processus de codage dans un cas particulier

 

Attention

dans l’étape 2 de la procédure.

Pour justifier le passage de  à , il faut effectuer le produit par la matrice .

.

 

Attention

 dans l’étape 3 de la procédure.

Pour justifier le passage de  à , il faut chercher le reste de la division de 55 par 26 et celui de 93 par 26 .

Or donc Ensuite donc .

 

Attention

dans l’étape 3 de la procédure.

Par conséquent, et .

Le passage de  à  est ainsi justifié.

>2. a) Un système de congruences

La transformation de  en  par le procédé de codage donne successivement :

 (étape 2 de la procédure),

et (étape 3 de la procédure).

De même, la transformation de  en  par le procédé de codage donne successivement :

 (étape 2 de la procédure),

et , (étape 3 de la procédure).

On obtient au final :

b) Résolution d’un système de congruences

Le système obtenu à la question précédente est équivalent à :

lui-même équivalent à

 

Attention

À développer et simplifier pour obtenir la deuxième ligne du système suivant.

Cela équivaut finalement à :

Ainsi, et .

Cela équivaut à dire que est un multiple de 26.

Or et sont des entiers compris entre 0 et 25.

Cela signifie donc que est égal à 0, soit . De même, .

>3.a) Identifier l’inverse d’une matrice



La matriceC est donc inversible et son inverse est bien la matriceC.

b) Effectuer un produit matriciel

.

c) Décodage dans un cas particulier

donc .

donc .

d) Conjecture sur le procédé général de décodage

On transforme  en  en calculant :



puis  est transformée en  telle que :

>4. Le problème du décodage dans le cas général

On a tout d’abord :

.

Si

alors

La matrice  se code bien en la matrice . Donc la matrice  se décode bien en .

>5. Décodage d’une séquence donnée

Les lettres QC se codent en .

On multiplie cette matrice par  :

.

On remarque ensuite que donc avec .

Puis donc avec .

Comme le nombre 4 code la lettre E, les deux lettres QC se décodent donc en EE.