Free Essay

Taking a File and Getting Out

In:

Submitted By mugiwara010
Words 8902
Pages 36
Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Codes d´tecteurs correcteurs e Arnaud Labourel
Courriel : arnaud.labourel@lif.univ-mrs.fr
Universit´ de Provence e 15 novembre 2011

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Coder et transmettre
Codage de l’information
Information cod´e par des 0 et des 1 e Codage transmis sous la forme de courants, ondes, etc.

Erreurs de transmission
Remplacements de 0 par 1 (et inversement)
Un bit par microseconde : accumulation d’erreurs de transmission taux d’erreur de 10−6 et connexion ` 1Mo/s, en moyenne 8 a bits erron´s transmis chaque seconde ! e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Exemples
Exemples concrets
Internet Protocole TCP : erreur d´tect´e, correction par e e retransmission Le CD Rayures ou impuret´s du support (peu fr´quentes e e mais tr`s volumineuses) : correction ` la vol´e e a e Le port s´rie Correction de petites erreurs relativement fr´quentes e e mais isol´es : correction imm´diate e e

Contraintes diverses
Faible coˆt d’implantation u Pas d’alt´ration de la vitesse de transmission e Fiabilit´ ! e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Quelles solutions ?
Agir sur le canal de transmission
Rendre le taux d’erreur n´gligeable e Impossibilit´ de remplacer toutes les infra-structures e existantes !
Taux nul impossible

Agir sur le message transmis
Etre capable de d´tecter si des erreurs ont eu lieu e Etre capable de les corriger au mieux
Principe des codes correcteurs d’erreurs
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

D´tecter et corriger les erreurs e D´tecter une erreur : et apr`s ? e e
Recommencer la transmission ?
Pas toujours possible
Manque de temps
Nouvelles erreurs possibles

Corriger l’erreur

Th´orie des codes e Comment coder les messages pour favoriser d´tection et correction e des erreurs de transmission
001110101011000111110000111111011011000111110010110001111100
000111000111101000111000111111111111000111000001111111000000
(01011010111101001100)
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Principe de la redondance
Pour me transmettre un num´ro de t´l´phone, parmi les solutions e ee possibles :
Message transmis
0654122235
zero six cinquante-quatre douze deux deux trente-cinq Message re¸u c 0654172236 zer0 slx cinquamte-quatte doyze deux deyx trsnte-c1nq Information concise : difficile ` corriger a Information redondante : d´tection et correction d’erreur e possible avec contexte !
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Exemples de redondances

Le plus souvent, r´p´tition du message ! e e
Au t´l´phone : ee R´p´tition des num´ros e e e Epeler le mot (A comme Abracadabra, R comme Ribambelle, etc.) Alphabet radio universel (Alpha Bravo Charlie Delta etc.)
Orthographe traditionnelle moins sensible aux erreurs que langage type SMS
Code g´n´tique e e

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Utilit´ du codage e D´tection et correction d’erreurs : redondance e Compression (abr´viations, code de Huffman, codec, e archivage, etc.)
Changement d’alphabets (code Morse, ASCII, etc.)
Cryptographie (rendre le d´codage difficile) e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Sch´ma g´n´ral de la communication e e e

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Formalisation du codage
Cas g´n´ral e e
Soient les alphabets An et B m .
Un codage est une application injective φ : An → B m

N´cessit´ de l’injection : d´codage e e e Soit M = φ(M).
D´codage : ` partir de M , retrouver M tel que φ(M) = M e a
Si ce M existe, il doit ˆtre unique ! e Cas du codage binaire
A = B = B, et m > n.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Addition modulo 2

Codage des messages = codage binaire
Un message de n bits = un mot binaire de longueur n
Op´rations classique de Bn e Un nouvel op´rateur dans B (XOR) e 0⊕0=0

0⊕1=1

1⊕0=1

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

1⊕1=0

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Addition modulo 2 (cont’d)
Propri´t´s
ee a⊕b =b⊕a

(1)

a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

(2)

a⊕0=a

(3)

a⊕a=0

(4)

a ⊕ b = c ⇐⇒ a ⊕ c = b ⇐⇒ b ⊕ c = a

(5)

De plus :

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Addition modulo 2 (cont’d)
Extension ` Bn a Si a = a1 a2 . . . an et b = b1 b2 . . . bn sont deux mots binaires, leur e somme modulo 2 est le mot binaire ayant pour p`me bit ap ⊕ bp . a b a⊕b 01001110
11011100
10010010

(on v´rifie dans Bn les propri´t´s 1 ` 5 en rempla¸ant 0 par le mot e ee a c binaire de taille n dont tous les bits sont nuls)

Poids w (a) d’un mot binaire a
Nombre de bits dans a ´gaux ` 1 : w (01100100001100001) = 6 e a
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

a ⊕ b indique une distance
Interpr´tation de a ⊕ b e a et b mots binaires de longueur n e p`me bit de a ⊕ b : 0 si ap = bp et 1 si ap = bp a ⊕ b indique les endroits o` a et b diff`rent u e w (a ⊕ b) indique le nombre de diff´rences e D´finition (Distance de Hamming) e La distance de Hamming entre deux mots binaires a et b de taille n est le poids de a ⊕ b. d(a, b) = w (a ⊕ b)
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Propri´t´s de la distance de Hamming ee Exemple d(111001111000, 101000111001) = 3

d(a, b) = d(b, a)

(sym´trie) e (6)

d(a, b) ≥ 0

(positivit´) e (7)

d(a, b) = 0

si et seulement si a = b

(8)

d(a, b) + d(b, c) ≥ d(a, c)

(in´galit´ triangulaire) e e

(9)

d(a ⊕ x, b ⊕ x) = d(a, b)
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

(invariance par translation) (10)
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Interpr´tation g´om´trique e e e
Alg`bre de Boole sur les mots binaires ! e El´ments de Bn dispos´s dans un n-cube : e e

Th´or`me e e
La distance d(a, b) est le nombre d’arˆtes qu’il faut longer pour se e rendre de a ` b par le chemin le plus court possible. a Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Vecteur d’erreur
Message envoy´ et message re¸u e c
Exp´diteur : message T de longueur n e Destinataire : message R de longueur p = n
Tout va bien si R = T , erreur de transmission si R = T

D´finition (Vecteur d’erreurs) e Le vecteur d’erreur entre un message transmis T et un message re¸u R est le vecteur e = T ⊕ R c w (e) = d(T , R) est le nombre de bits mal transmis.
T = e ⊕ R et R = T ⊕ e
Exemple : e = 1011 ⊕ 1101 = 0110
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Code et mots de code
D´tecter une erreur de transmission ? e Si destinataire connaissait e, il pourrait retrouver T !
Mais e reste inconnu !
Accord entre exp´diteur et destinataire sur certaines e particularit´s de messages e D´finition du code C : ses ´l´ments sont des mots de code e ee
Le code favorise la d´tection d’erreurs, dans le cas o` R ∈ C e u
Erreurs non reconnues si R ∈ C pourtant erron´ e Exemple : triplement de chaque bit
T = 000111111111, R = 000111111000 ∈ C
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Corriger une erreur de transmission ?
Ensemble des vecteurs d’erreur possibles pour R
Le destinataire connaˆ C et R ! ıt Il peut d´terminer Γ(R) = {C ⊕ R|C ∈ C} : e ∈ Γ(R) e Exemple : R = 000110, C = {m.b}. o` chaque bit est tripl´ u e
C = {000000, 000111, 111000, 111111}, Γ(R) = {000110, 000001, 111110, 111001}

Une approche probabiliste pour corriger
Le destinataire souhaite corriger R si une erreur est suspect´e e Il sait que e ∈ Γ(R), mais ne peut le connaˆ avec certitude ıtre Paris de corrections avec ´valuation des risques e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Estimation des risques ?
Canal binaire
Dispositif pour la transmission de bits
Risque d’erreur d’un canal binaire estim´ par e p=

nombre de bits faux nombre de bits transmis

Exp´dition d’un bit = ph´nom`ne al´atoire ` deux issues e e e e a 1. Le bit est bien transmis
2. Le bit est mal transmis

Probabilit´ d’erreur du canal = p e q =1−p p tr`s petit (sauf si canal tr`s mauvais !) e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Quelques hypoth`ses sur le canal e Canal sym´trique e p identique, que l’on transmette des 0 ou des 1
Pas toujours valable (pr´sence ou absence de trous sur un e CD...)

Canal sans m´moire e Les erreurs ne se groupent pas et mˆme r´partition des erreurs e e
Transmission de chaque bit ind´pendante des autres e Pas toujours valable non plus !

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Transmission d’un message : un ph´nom`ne al´atoire e e e Exp´dition d’un mot binaire de longueur n = r´p´tition n fois e e e de l’exp´dition d’un bit : bien ou mal transmis e Issues du ph´nom`ne al´atoire E = vecteurs d’erreur e e e Nombre d’erreurs E suit une loi binomiale B(n, p)

Rappels
Soit Φ un ph. al´a. ne comprenant que deux issues, X et Y , muni e d’une loi p. Soit x = p(X ) et y = p(Y ), avec y = 1 − x.
Si n essais r´p´t´s sont ind´pendants, alors : e ee e p(M) = x k y n−k si M est un mot particulier (cible connue) contenant k issues X et n − k issues Y k p(M) = Cn x k y n−k si M est un mot quelconque contenant k issues X et n − k issues Y .
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

En pratique...
Soit un canal sur lequel le taux d’erreurs p = 10−2 (et q = 0.99).
Envoi de messages de 64 bits sur ce canal

Probabilit´ d’avoir : e aucune erreur de transmission :
P(E = 0) = (1 − p)n = q n = 0.9964 ∼ 0, 526 une seule erreur : P(E = 1) = np(1 − p)n−1 ∼ 0, 340 deux erreurs : P(E = 2) = trois erreurs : P(E = 3) =

n(n−1) 2 p (1 − p)n−2 ∼ 0, 108
2
3
Cn p 3 (1 − p)n−3 ∼ 0, 023

plus de 4 erreurs : P(E > 4) < 0, 0005
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

R´sultat fondamental e Th´or`me e e
Lorsque l’on transmet des mots binaires de longueur n sur un canal binaire sym´trique et sans m´moire, dont la prob. d’erreur est p : e e
1. Si l’on se donne e, la probabilit´ que le vecteur d’erreur soit e e est p w (e) q n−w (e)
2. Si l’on se donne k, la probabilit´ que le nombre d’erreurs de e k transmission soit k est : Cn p k q n−k
3. Si l’on transmet T , la probabilit´ de recevoir R est e p d(T ,R) q n−d(T ,R)

Exemple
On transmet T = 0110, soit p = 0.001 : visualisons p(R) et le nombre d’erreurs d
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Probabilit´s de R, T = 0110, p = 0.001 e R
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

d
2
3
1
2
1
2
0
1
3
4
2
3
2
3
1
2

P(R) p2 q2 p3 q1 p1 q3 p2 q2 p1 q3 p2 q2 p0 q4 p1 q3 p3 q1 p4 q0 p2 q2 p3 q1 p2 q2 p3 q1 p1 q3 p2 q2

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

valeur (p = 0.001)
0.0000009 . . .
0.0000000009 . . .
0.0009 . . .
0.0000009 . . .
0.0009 . . .
0.0000009 . . .
0.9 . . .
0.0009 . . .
0.0000000009 . . .
0.000000000001 . . .
0.0000009 . . .
0.0000000009 . . .
0.0000009 . . .
0.0000000009 . . .
0.0009 . . .
0.0000009 . . .
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Comment d´tecter et corriger ? e Interpr´tation e p q : probabilit´ de substitution de M1 par M2 diminue e tr`s vite quand d(M1 , M2 ) augmente e Plus le poids de e augmente, moins il est probable
Id´e : e est l’´l´ment de Γ(R) de plus faible poids e ee
Remplacer le mot re¸u par le mot vraisemblable le plus proche c Strat´gie : un pari e 1. e est le mot de plus petit poids dans Γ(R)
2. Remplacement de R par T = e ⊕ R (e = 0 si T = R)
Correction la plus vraisemblable, mais pas toujours valable
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Exemple : mots 0xx · · · x0
Soit C = {0000, 0010, 0100, 0110}
R´ception de R = 0111, R ∈ C e Calcul de Γ(R) :
Γ(R) = {0000 ⊕ 0111, 0010 ⊕ 0111, 0100 ⊕ 0111, 0110 ⊕ 0111}
Γ(R) = {0111, 0101, 0011, 0001} e 0111
0101
0011
0001

w (e)
3
2
2
1

P(e) p3 q p2 q2 p2 q2 pq 3

T
0000
0010
0100
0110

Choix de e de plus petit poids
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Codage par blocs : tr`s r´pandu e e
L’exp´diteur : e 1. D´couper le message binaire en blocs (paquets de bits) de e longueur fixe
2. Coder chaque bloc avec ajout de bits de contrˆle : mots de o code
3. Envoi des mots de code

Le receveur
1. R´ception des mots de code et d´tection d’erreur (le mot e e est-il un mot de code ?)
2. Correction ´ventuelle du mot re¸u en le rempla¸ant par le mot e c c de code le plus proche
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr
Codes e
3. Extraction des blocs : d´codage d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Constitution du mot de code
Codage des blocs
Bloc de dimension k = un mot binaire de longueur k
Ajout de r bits de contrˆle (ou bits de parit´) o e
Obtention de mots binaires de longueur n = k + r
Mots de code de taille n ⊆ mots binaires de taille n

Codage syst´matique e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Codage = application
Quelle application ?
Ensemble des blocs = Bk , ensemble des messages = Bn
2k mots de codes et 2n messages
Codage = φ : Bk → Bn associe un mot de code ` un bloc a Rendement (taux) d’un code
Proportion du bits d’information parmi les transmis τ =

k n Le plus ´lev´ possible e e
M´taphore du colis : r´sistance (poids) et prix de l’emballage e e
Compromis s´curit´ vs. coˆt de l’envoi e e u proportion de mots de code = 2k /2n = 2k /2k+r = 1/2r
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Test de parit´ e Principe
Un bit de contrˆle pour garantir la parit´ du nombre de 1 (r = 1) o e
Dans le cas k = 3 : n = 4 et τ = 3/4
Exemple :Φ(001) = 0011, Φ(110) = 1100

Mots de codes

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Test de parit´ (cont’d) e Exemples de (non-)d´tection e R´ception de R = 1011 : une ou trois erreurs commises e R´ception de R = 1111 : aucune, 2 ou 4 erreurs commises e Semble correct : on laisse passer !

Correction impossible
Si erreur d´tect´e, le bit de contrˆle ne fournit aucune information e e o sur l’endroit de l’erreur
C = {0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111}
R = 1011 ∈ C une ou trois erreurs ?
4 vecteurs d’erreur de poids 1 = {1000, 0010, 0001, 0100}
T les plus vraisemblables : T ∈ {0011, 1001, 1010, 1111}
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Test de parit´ (cont’d) e Risque pris lors de l’acceptation d’un mot de code p(R = T ) = q 4 , p(R = T ) = 1 − q 4 = 1 − (1 − p)4 = 4p − 6p 2 + 4p 3 − p 4
Cas d’erreur de jugement : si 2 ou 4 erreurs p(deux erreurs) = 6p 2 q 2 , p(quatre erreurs) = p 4 donc p(laisser passer un message faux) = 6p 2 q 2 + p 4

Proportion de messages faux non d´tect´s (FP) : e e
6p 2
6p 2 − 12p 3 + 7p 4

∼ 1.5p si p petit
4p − 6p 2 + 4p 3 − p 4
4p
Si p = 0.001 : 0, 15% de FP (vs. 100% sans codage !)
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Codage par r´p´tition e e
Principe
Bits d’informations transmis un ` un, mais en les triplant. a Φ(1) = 111, Φ(0) = 000, Φ(01) = 000111
Avec k = 1, r = 2, n = 3, pauvre rendement τ = 1/3

Taux de d´tection (cas de deux mots de codes) e Si T = 000 et R = 111, l’erreur n’est pas d´tect´e ! e e p3 p(faux non d´tect´s) = 3p−3p2 +p3 ∼ p 2 /3 e e quand p est petit.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e S´curisation de la transmission d’informations e Distance de Hamming
Erreurs de transmission
Codage par blocs

Codage par r´p´tition (cont’d) e e
Capacit´ de correction e 3 bits faux ils sont accept´s, pas de correction e 2 bits faux majoritaires, donc le troisi`me est corrig´ e e
1 bit faux minoritaire, il est corrig´ e pas de bit faux pas de correction. p(mauvaise correction) = p 3 + 3p 2 q = 3p 2 − 2p 3

Proportion de messages faux qui le restent apr`s correction e 3p 2 − 2p 3
∼p
3p − 3p 2 + p 3
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

R´capitulatif e Pari que l’erreur commise est l’erreur la plus probable

M´thode pratique pour corriger un message e 1. D´terminer Γ(R) (vecteurs d’erreurs pour R) e 2. D´terminer le message de plus faible poids dans Γ(R) e 3. Ajout modulo 2 (⊕) de ce message ` R : obtention du mot de a code le plus vraisemblable qui remplacera R

Sur un n-cube
Rep´rer le message M ∈ C le plus proche de R e Quid en cas d’ex-aequo ?
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

Visualisation des corrections concurrentes

R´p´tition e e

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Parit´ e Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

Distance minimale
D´finition (Distance minimale) e La plus petite distance s´parant deux mots de code distincts est e appel´e la distance minimale du code, not´e d. e e

Exemples
Test de parit´ : d = 2 e Codage par r´p´tition : d = 3 e e

Th´or`me e e
Le receveur d´tecte de fa¸on certaine TOUS les messages faux, e c tant que le nombre d’erreurs N v´rifie 0 < N < d. e Certains messages faux comportant d erreurs (ou plus) ne sont pas d´tect´s. e e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

Distance minimale (cont’d)
Th´or`me
e e
Les messages sont bien corrig´s tant que le nombre d’erreurs N e v´rifie 0 ≤ N < d/2 (strict). e Les messages faux tels que d/2 ≤ N ne sont pas toujours bien corrig´s. e

Exemple

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

Nombre d’erreurs corrig´es e t = d/2 = d 1
2
3
4
5
6

t
0
0
1
1
2
2

d
1 − (−1)d

2
4

D’apr`s le th´or`me pr´c´dent : e e e e e
Tout message faux ayant t erreurs ou moins est corrig´ de fa¸on parfaite e c
Il existe des messages faux mal corrig´s qui ont t + 1 erreurs e La correction peut parfois ˆtre bonne e mˆme si N > t e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

Triplet de description d’un code [n, k, d]
Exemples
Test de parit´ : code [4, 3, 2] e Codage par r´p´tition : [3, 1, 3] e e

Int´rˆt d’une grande d ee Pour plus de d´tection et de correction d’erreurs e Mots de code ´loign´s e e
Si k est fix´ : nombre de mots de code fix´ e e
Si k fix´ : intercaler le plus possible de messages entre mots e de code : augmenter n, mais alors k/n diminue !
Bon code : d et n grands
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

Interpr´tation sur les n-cubes e k et r fix´s. Donc Bn fix´ : tous les messages possibles, mots de e e code ou pas.

A r´soudre e Comment marquer d’un point bleu 2k sommets d’un n-cube de telle sorte que tous les sommets bleus soient le plus ´loign´s e e possible les uns des autres ?

Exemples : k = 1, r = 2, d ∈ {1, 2, 3}

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

In´galit´ de Hamming e e
Objectif, n fix´ e Majorer t, donc d
On a toujours d ≤ n, mais grossier !

In´galit´ de Hamming e e
Les quantit´s n, r , et t, sont li´es par l’in´galit´ de Hamming : e e e e
0
1
2
t
Cn + Cn + Cn + · · · + Cn ≤ 2r p Soit message M de taille n, et p ≤ n, il y a exactement Cn messages situ´s ` la distance p de M (modification de e a

p bits parmi n) ; Consid´rons la sph`re S(M, m) des messages situ´s ` une distance plus petite que m de M : e e e a
0
1 m nombre de messages dans S(M, m) = Cn + Cn + · · · + Cn . On cherche h tq l’intersection de S(Ci , h) et

S(Cj , h) soit vide pour tous mots de code Ci et Cj diff´rents : h = t. Il y a 2k sph`res S(C , t) centr´es sur les e e e 0
1
t mots de code. Donc 2k (Cn + Cn + · · · + Cn ) ≤ 2n ).

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

Borne de Hamming
Majoration de t
1. Calculer, dans l’ordre :
0
1 u0 = Cn u1 = u0 + Cn r d´passer 2 e 2 u 2 = u 1 + Cn

···

Jusqu’` a 2. Le premier indice m t.q. um > 2r est un majorant strict de t
(convergence assur´e car un = 2n > 2r ) e Borne de Hamming d ≤ 2m
Exemple : r = 1 u0 = 1 ≤ 2, u1 = 1 + n ; or n ≥ 2 puisque n = k + r . Donc u1 ≥ 3 > 2r . Majoration obtenue : 1 > t !
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Mesures de codages et r´sultats e Vers un bon codage

Code parfait
Egalit´ de Hamming e 0
1
2 t Cn + Cn + Cn + · · · + Cn = 2r ⇐⇒ les 2k sph`res S(C , t) forment e n. une partition de B

D´finition (Code parfait) e Un code est parfait s’il v´rifie l’´galit´ de Hamming. e e e d(M, C ) ≤ t
Exp´dition de C , r´ception de R : e e soit d(C , R) ≤ t : le message est bien corrig´ e soit d(C , R) > t : le message est mal corrig´ e Un code parfait ne corrige jamais plus que t erreurs

Exemple : code par r´p´tition [3,1,3] e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Codes lin´aires e D´finition (Code lin´aire) e e
Un code C est lin´aire lorsque Ci ⊕ Cj = Ck o` Ci , Cj et Ck sont e u des mots du code.

Cons´quence e Quand un code est lin´aire, 0...0 est toujours un mot de code. e Exemples : test de parit´, code par r´p´tition e e e
Facilit´ pour d´terminer d e e
La distance minimale d est le poids du mot de code non nul de plus petit poids d(C1 , C2 ) ≥ d
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Codage lin´aire e D´finition (Codage lin´aire) e e
Soit les blocs ui . Un codage est lin´aire quand l’application φ e v´rifie : e φ(u1 ⊕ u2 ⊕ · · · ⊕ up ) = φ(u1 ) ⊕ φ(u2 ) ⊕ · · · ⊕ φ(up ), ∀p ≥ 1

Remarques somme de blocs = somme de leur mots de code par r´currence : φ(a ⊕ b) = φ(a) ⊕ φ(b) e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Codage lin´aire (cont’d) e D’o` vient l’appellation lin´aire u e
(B,⊕,∧) est un corps
Bn est un espace vectoriel de dimension n sur ce corps
Code lin´aire = sous-espace vectoriel de Bn e Codage lin´aire : application Bk → Bn e Code ou codage lin´aire : th´or`me e e e
1. Codage lin´aire : son code est lin´aire, et 0...0 est le mot de e e code associ´ au bloc nul e 2. Codage syst´matique, de code lin´aire, est lin´aire. e e e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Simplification propre aux codes lin´aires e Codage non-lin´aire : besoin des 2k mots de code pour coder e chaque bloc
Codage lin´aire : k mots de code suffisent (base canonique) e D´finition (Base canonique de code) e b1 =1000 ... 00 b2 =0100 ... 00
= .... ... bk−1 =0000 ... 10 bk =0000 ... 01
(b1 , b2 , · · · , bk ) forme la base canonique de Bk
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Base canonique de code lin´aire [7, 4] : code Cycl e φ(1000) = 1000101, φ(0100) = 0100111, φ(b3 ) = 0010110 et φ(b4 ) = 0001011 b1 b2 b4 b

1000
0100
0001
1101

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

φ(b1 ) φ(b2 ) φ(b4 ) φ(b) 1000101
0100111
0001011
1101001

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Repr´sentations matricielles e Motivation
D´terminer un mot de code ` partir d’un bloc = produit de e a matrices Matrice g´n´ratrice (codages syst´matiques) e e e Ik : matrice identit´ de taille k e P (r colonnes) : matrice de parit´ (bits de contrˆle) e o

Notation : b = 0 1 0 0 1 = 01001
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Matrices g´n´ratrices : exemples e e
Test de parit´ e 


1 0 0 1
G = 0 1 0 1
0 0 1 1

 
1
P = 1
1

Codage par r´p´tition e e
G= 1 1 1

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

P= 1 1

Codes d´tecteurs correcteurs e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Concepts fondamentaux
Correction et d´tection e Codes lin´aires e Matrices g´n´ratrices : exemples (cont’d) e e

Code Cycl


1
0
G =
0
0

0
1
0
0

0
0
1
0

0
0
0
1

1
1
1
0

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

0
1
1
1


1
1

0
1


1
1
P=
1
0

0
1
1
1

Codes d´tecteurs correcteurs e 
1
1

0
1

Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Codage lin´aire d´fini par P ! e e
Codage tr`s simple ! e Sp´cifier kr valeurs (bits) au lieu de 2k r dans le cas g ´n´ral e e e des codages syst´matiques e Calcul facile du code d’un bloc
Le mot de code φ(b) est repr´sent´ par la matrice ligne bG e e
(produit de b par matrice G )

Exemple : test de parit´, codage de 101 e 

1 0 0 1
1 0 1 0 1 0 1 = 1 0 1 0
0 0 1 1
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Correction des codes lin´aires e R´ception de R, calcul de Γ(R), recherche du mot e de plus petit e poids dans Γ(R), et calculer e ⊕ R.

Objectif
Optimiser la rapidit´ de correction : enregistrer les actions e r´p´t´es, et les lire quand on en a besoin (au lieu de les recalculer) e ee

Th´or`me e e
1. La relation d´finie sur Bn par : u v quand u ⊕ v est un e mot de code, est une relation d’´quivalence e 2. Elle poss`de 2r classes d’´quivalence e e
3. Γ(R) est la classe d’´quivalence de R e 4. Le code C est la classe de 0...0
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Correction des codes lin´aires : tableau standard e Cons´quence du th´or`me e e e
Les ensembles Γ(R) forment une partition de Bn

Id´e ing´nieuse de stockage des Γ(R) e e
Construction d’une table de correction : le tableau standard
Regrouper les mots de Bn par classe
Rep´rer le mot de plus faible poids dans chaque classe e Structure du tableau standard
2r lignes (contrˆle), 2k colonnes (blocs) o Rangement des ´l´ments, de telle sorte que : ee 1. une ligne contient une classe d’´quivalence e 2. l’´l´ment le plus ` gauche est celui de plus faible poids ee a
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Construction du tableau standard
M´thode pratique e 1. Ranger les mots de Bn par poids croissants (si ex-aequo : ordre lexico) : obtention d’une liste B
2. Dessiner un tableau de 2r lignes et 2k colonnes
3. Ranger les mots de code (taille n) dans la premi`re ligne, en e conservant l’ordre qu’ils ont dans B (donc 0..0 ` gauche !) a 4. Tout ` gauche de la premi`re ligne vide , placer le premier a e
´l´ment qui reste dans B. ee 5. Remplir chaque case de en additionnant premier ´l´ment de ee la ligne, et ´l´ment au dessus de la case en premi`re ligne. ee e
6. Quand une ligne est remplie, recommencer la mˆme op´ration e e ligne suivante.
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Construction du tableau standard (cont’d)
Structure

Tableau standard du code de parit´ [4, 3, 2] e 0000
0001

0011
0010

0101
0100

0110
0111

1001
1000

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

1010
1011

1100
1101

Codes d´tecteurs correcteurs e 1111
1110

Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Construction du tableau standard (cont’d)
Exemple du code par r´p´tition [3, 1, 3] e e
000
001
010
100

111
110
101
011

Propri´t´ ` retenir eea Chaque ligne ´nonce Γ(R) pour tous les messages re¸us R de e c cette ligne
Dans une ligne, les mots sont ordonn´s par ordre croissant de e poids !
Si on re¸oit R pr´sent sur la ligne i colonne j, la correction c e sera vers R ⊕ ei = Cj !
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Comment corriger ` partir du tableau standard a M´thode pratique de correction e 1. Chercher la position (i, j) du message re¸u R c 2. Remplacer le message R par le mot de code de la mˆme e colonne, sur la premi`re ligne e Exemple sur code de parit´ [4, 3, 2] e (d faible)
On remplace R = 1000 par M = 1001
On remplace R = 0001 par M = 0000
Pas toujours satisfaisant ! Pourquoi ne pas remplacer 0001 par 1001 ou 0101, ou...
Sur code par r´p´tition : plus juste e e
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Tableau standard : peut mieux faire
Observations
Le tableau standrard peut ˆtre gigantesque ! e Seules les premi`res lignes sont exploit´es (mots de faible e e poids) N´cessit´ d’une alternative e e

Matrice de contrˆle H o Privil´gions les calculs sur le stockage e Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Exemples de matrices de contrˆle o Parit´ [4, 3, 2] e  
1
1 tH =  
1
1

R´p´tition [3, 1, 3] e e



1 1 t H = 1 0
0 1

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Cycl

1 0
1 1

1 1

t H = 0 1

1 0

0 1
0 0

Codes d´tecteurs correcteurs e 
1
1

0

1

0

0
1

Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Notion de syndrome
D´finition (Syndrome du message m = a1 a2 . . . an ) e Le syndrome de m, est σ(m) = mt H
On a : σ(m ⊕ n) = σ(m) ⊕ σ(n)

Exemple : codage par r´p´tition [3, 1, 3] e e


1 1 σ(101) = 1 0 1 1 0 = 1 0
0 1

message
011
101
110

syndrome
11
10
01

Remarque
Lignes de t H = tous les syndromes des messages de poids 1
Sommes 2 ` 2 des lignes de t H = syndromes des messages de a poids 2, etc.
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Utilit´ des syndromes e Th´or`me e e
M1 M2 ⇐⇒ σ(M1 ) = σ(M2 )

Cons´quence e On attache un syndrome ` chaque classe d’´quivalence a e
2r syndromes : tous les mots de r bits sont des syndromes

Correction rapide d’un message
Remplacement du tableau standard
Liste des syndromes : ` chaque 2r mots a faible poids dont le mot est le syndrome
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

message de plus

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Etablir les liste des syndromes

M´thode pratique e 1. Ranger en colonne tous les mots binaires de longueur r (ordre lexico) : les syndromes. Pr´voir une seconde colonne ` cˆt´. e a oe
2. Construire B : ´l´ments de Bn rang´s par poids croissants ee e
3. Pour chaque b ∈ B (dans l’ordre) : calculer σ(b). Si la place est libre dans la seconde colonne en face de σ(b), y inscrire b.
4. Stop quand seconde colonne emplie.

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Exemple dans le cas de Cycl

b1 b2 b3 b4 = 1000,
= 0100,
= 0010,
= 0001,

φ(1000) = 1000101 φ(0100) = 0100111 φ(0010) = 0010110 φ(0001) = 0001011

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

syndrome
000
001
010
011
100
101
110
111

Codes d´tecteurs correcteurs e message
0000000
0000001
0000010
0001000
0000100
1000000
0010000
0100000

Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

D´roulons l’exemple e 2r

Mots
000
001
010
011
100
101
110
111
Calculons σ(0000000)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Calcul de σ(0000000)

1
1

1
 σ(0000000) = 0 0 0 0 0 0 0 0

1

0
0

t
0⊕0⊕0⊕0⊕0⊕0⊕0
= 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
0⊕0⊕0⊕0⊕0⊕0⊕0

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

0
1
1
1
0
1
0


1
1

0

1

0

0
1

0 0

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

D´roulons l’exemple (cont’) e 2r

Mots
000 0000000
001
010
011
100
101
110
111
Calculons σ(0000001)

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Calcul de σ(0000001)

1
1

1
 σ(0000001) = 0 0 0 0 0 0 1 0

1

0
0

t
0⊕0⊕0⊕0⊕0⊕0⊕0
= 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
0⊕0⊕0⊕0⊕0⊕0⊕1

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

0
1
1
1
0
1
0


1
1

0

1

0

0
1

0 1

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

D´roulons l’exemple (cont’) e 2r

Mots
000 0000000
001 0000001
010
011
100
101
110
111
Calculons σ(0000010)...

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Calcul de σ(0000010)

1
1

1
 σ(0000010) = 0 0 0 0 0 1 0 0

1

0
0

t
0⊕0⊕0⊕0⊕0⊕0⊕0
= 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 = 0
0⊕0⊕0⊕0⊕0⊕0⊕0

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

0
1
1
1
0
1
0


1
1

0

1

0

0
1

1 0

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

D´roulons l’exemple (cont’) e 2r

Mots
000 0000000
001 0000001
010 0000010
011
100
101
110
111
Calculons σ(0000100)...

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Calcul de σ(0000010)

1
1

1
 σ(0000100) = 0 0 0 0 1 0 0 0

1

0
0

t
0⊕0⊕0⊕0⊕1⊕0⊕0
= 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 1
0⊕0⊕0⊕0⊕0⊕0⊕0

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

0
1
1
1
0
1
0


1
1

0

1

0

0
1

0 0

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

D´roulons l’exemple (cont’) e 2r

Mots
000 0000000
001 0000001
010 0000010
011
100 0000100
101
110
111
Calculons σ(0001000)...

Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Messages 2n
0000000
0000001
0000010
0000100
0001000
0010000
0100000
1000000
0000011
···
1111111
Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Corriger avec les syndromes
Principe
Avec R re¸u : on le corrige en lui ajoutant l’´l´ment de Γ(R) de c ee plus petit poids, donc l’´l´ment de Bn qui a le mˆme syndrome que ee e
R avec le plus petit poids possible.

M´thode pratique pour corriger R e 1. Calculer σ(R)
2. Rep´rer S : le message associ´ ` σ(R) dans la liste. e ea
3. Corriger R en le rempla¸ant par R ⊕ S c Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Exemple avec Cycl
Soit R = 1010101,


1
1

1
 t σ(R) = R H = 1 0 1 0 1 0 1 0

1

0
0

0
1
1
1
0
1
0


1
1

0

1 = 1 1 0

0

0
1

Avant derni`re ligne de la liste des syndromes : M = 0010000 e C = 1010101 ⊕ 0010000 = 1000101
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e Concepts fondamentaux
Correction et d´tection e Codes lin´aires e D´finition et principes e Repr´sentations matricielles e Tableau standard
Matrice de contrˆle et syndrome o Construction de bons codes correcteurs

Code parfait
Un code correcteur parfait doit corriger parfaitement les messages qui n’ont qu’une erreur : t ≥ 1 ou d ≥ 3

Th´or`me e e
Un codage lin´aire corrige de fa¸on certaine toutes les erreurs de e c t H a toutes ses lignes distinctes et non poids 1 ⇐⇒ sa matrice nulles. Les lignes de t H sont les syndromes des messages de poids 1 : pas de mot de code de poids 1 ⇐⇒ pas de ligne nulle dans t H

D´finition (Code de Hamming) e Un code de Hamming est un code lin´aire [2r − 1, 2r − 1 − r ] dont la matrice e t
H est constitu´e de tous les mots binaires non nuls de longueur r . e d =3
Code parfait
Arnaud Labourel, arnaud.labourel@lif.univ-mrs.fr

Codes d´tecteurs correcteurs e

Similar Documents

Premium Essay

Nt1330 Unit 1 Assignment 1

...frameworks what every authorization accomplishes for both organizers and documents. Full control: The client has full control to the organizer and can include, change, move and erase things. The client can likewise include and evacuate authorizations the organizer and for any subfolders. The stressed sentence is vital to remember. This authorization level can be hazardous in the wrong hands. The client has full control to the file and can change, move or erase it. The client can likewise include and expel permissions the file. Modify: A blend of Read and Write authorizations. A client...

Words: 1870 - Pages: 8

Free Essay

Dgfg

...Point 2. Note Taking 4. Describe your present note taking strategies in your classes. How well is your approach working for you. Do your notes help you pass your quizzes/exams? Do you feel you need to improve your note taking skills? My note taking is on point at the moment, I believe I am great at note taking & organized as well as detailed when I write down notes. My notes help me better understand the book than having to read, when it comes to exams & quizzes I rely on my notes to help me pass 5. Review Chapter 5 and select strategies that you think will help you. Practice using the new strategies for a week. Report on the results. Did you notice any improvements in your learning and understanding of the course materials? The strategy I selected to use was the Cornell system, it helped me better understand what I am listing to and what I am writing down. 3. Watch Video, Julian Treasure: 5 Ways to Listen Better. Using your word processor, write two paragraphs. 1. Julian Treasure gives several compelling reasons why good listening skills are important. Summarize these reasons. 2. Use the 4 RASA techniques on one person this week and describe what you did and how they reacted. Good listening skills are important because with out listening we are not able to experience the flow of time from past to future. Without listening our world will become a very scary place. If we were to listen, media sources wont have to scream out to us to catch our...

Words: 984 - Pages: 4

Free Essay

Paper

...within the workplace has transformed work arrangements and habits. There are many examples of theft of time including sleeping on the job, taking a longer lunch, and even taking care of personal responsibilities during work hours. “Time theft costs employers more than $400 billion per year in lost productivity” (Donskey). One of the biggest factors in theft of time is the internet. Employees have easy access to the internet, from work issued computers to the use of smart phones. Unfortunately, with the use of personal cell phones, even with policies put into place to prevent and/or prohibit the use of cell phones during work hours, is usually not enough to stop many employees. Furthermore, these forms of theft of time typically go unnoticed by companies but policies and other means of prevention can be put in place to deter employees from such activities. Many companies block out popular websites, such as social media websites or some competitor websites. Also, computers issued by the company are company property and are monitored. When employees know their internet usage is being watched, they are more careful with what they attempt to access on the internet during work hours. To monitor hours worked, and when lunch breaks are taken, all employees are typically issued employee id numbers. The employees use this number to sign in and out of work and their time is tracked. This way it helps prevent long lunch breaks and makes sure employees are working during their scheduled...

Words: 1490 - Pages: 6

Premium Essay

Asgmnt Wk 2

...within the workplace has transformed work arrangements and habits. There are many examples of theft of time including sleeping on the job, taking a longer lunch, and even taking care of personal responsibilities during work hours. “Time theft costs employers more than $400 billion per year in lost productivity” (Donskey). One of the biggest factors in theft of time is the internet. Employees have easy access to the internet, from work issued computers to the use of smart phones. Unfortunately, with the use of personal cell phones, even with policies put into place to prevent and/or prohibit the use of cell phones during work hours, is usually not enough to stop many employees. Furthermore, these forms of theft of time typically go unnoticed by companies but policies and other means of prevention can be put in place to deter employees from such activities. Many companies block out popular websites, such as social media websites or some competitor websites. Also, computers issued by the company are company property and are monitored. When employees know their internet usage is being watched, they are more careful with what they attempt to access on the internet during work hours. To monitor hours worked, and when lunch breaks are taken, all employees are typically issued employee id numbers. The employees use this number to sign in and out of work and their time is tracked. This way it helps prevent long lunch breaks and makes sure employees are working during their scheduled...

Words: 1491 - Pages: 6

Free Essay

When Faced with Growth

...Information or PII is information that can be used to distinctively identify, contact, or locate an individual. PPI is sensitive information that is associated with a person. These information should be accessed only on a strict need-to-know basis and handled and stored with great care. Personally identifiable information is information that can be used to distinguish or trace an individual's identity, such as their name, social security number, biometric records, etc., alone, or when combined with secondary personal or secondary identifying information that is linked or linkable to a specific individual, such as date and place of birth, mother's maiden name, etc. Most companies keep sensitive personal information in their hard copy files such as names, addresses, gender, social security numbers, credit card, or other account data that uniquely identifies customers or employees (Heller, 2001, p. 1). This information is often necessary to complete customers’ orders, meet payroll, or perform other important business functions. However, if sensitive information gets into the wrong people, there is every tendency that it can lead to fraud, or identity theft. The cost of defending a security breach is alarming. Gaining the trust of customers and prospective customer may be a very difficult task. Some companies may have a division in the organization that takes care of protecting PII. Others businesses hire an outside contractor in safeguarding their sensitive information...

Words: 942 - Pages: 4

Free Essay

Pos355

...Windows Memory Management, Process Management, File Management, Security Jose Rodriguez POS/355 July 25, 2015 Yevgeniy Tovshteyn Windows Memory Management The Widows 32-bit OS adds a virtual memory system, which is based on a flat 32-bit address space. The 32-bits of address space converts into the 4GB of virtual memory. The 4GB is the amount that can be accessed by a process. The Windows operating system has Kernel-mode and User-mode memory ("Memory Management 101", 2007). If you exceed the memory limit you will get an "out of virtual memory" error and this would show even though you have a lot of physical memory. The Kernel space is the system space portion of the address space in the OS and kernel-mode drivers reside. This is where only the kernel-mode can access this space. The User-mode can only access data that is within their own process ("Need More Memory? Getting Started With Windows Memory Management", n.d.). This means that the User-mode threads cannot have access to data from another process space directly and it's not able to access the system space directly. The interesting thing about the kernel-mode drivers is that they are trusted by the OS and is able to access both the kernel and user space ("Memory Management 101", 2007). Windows Process Management In process management each process provides a measure to execute a program. The process management has an independent virtual address space that contains both data and code that are protected. Each process...

Words: 803 - Pages: 4

Premium Essay

Arguing for the Right to Download Free Music

...ITM 434 Module I: Case Assignment If it is ok for a starving man to steal food if he has no money, why can’t a person download free music if he or she feels the price is too high? Peer to peer downloading and file sharing is one of the most popular uses of the internet within today’s generation. The downloading and sharing of files takes place in networks such as Limewire, Kazaa, or Edonkey which provide individuals the opportunity to search and download from others on an unlimited basis. One of the important features that have lead to the success and popularity of this medium of getting music is the variety of music itself. Since there are so many people sharing and downloading music, the variety of music is greater, giving the user a various selection of music files to choose from. Another aspect of the sharing and downloading of music over the internet that has made it very popular is that it can perceived as a win-win situation for both parties involved. The record companies are trying to put a stop to music downloading, they feel it is stealing copyrighted music they produced, even going as far as taking legal action on people who have downloaded their music. Is this just greed from the record companies? Accord to Allen Steven of the Los Angeles Times, album sales are not the top grossing income for artists and artists only receive one percent of record sales (08/21/00). The rest goes straight to the record companies. Record companies are making millions on record...

Words: 1447 - Pages: 6

Premium Essay

Translating a Letter

...Translating a Letter CMGT/554 Dr. Jairo Garcia University of Phoenix August 30th, 2015 By Scott Schuelke 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 Much like electricity, radio waves transmit the information in the form of pulses. In this case there is no voltage or amperes to produce watts of power. With radio or sound waves there is amplitude the decibels (dB) of the wave, frequency (Hz) the number of waves per second, and the phase or direction in which the wave begins. As the radio or sound wave dB increases it causes a spike to indicate the value of 1 in this representation, a normal pulse of sound with no spike represents a 0 along the phase. Much like electricity, radio waves transmit the information in the form of pulses. In this case there is no voltage or amperes to produce watts of power. With radio or sound waves there is amplitude the decibels (dB) of the wave, frequency (Hz) the number of waves per second, and the phase or direction in which the wave begins. As the radio or sound wave dB increases it causes a spike to indicate the value of 1 in this representation, a normal pulse of sound with no spike represents a 0 along the phase. -5 volts -5 volts +5 volts +5 volts Electrical transmission of the letter “A” using the ASCII numbering for the letter A. In the electrical diagram a positive voltage resembles the number 1 and the negative side a 0. In this case the ASCII unit for the letter A would be 01000001. A copper wire transmits electricity...

Words: 2069 - Pages: 9

Premium Essay

Gram

...Hardik Raval (0165421) MG 670 – 102 October 29, 2015 'The Labor Debate:’ The American Dream Revisited Immigration is one hot topic in modern day conversation. Many believe that immigrants coming to the United States are taking many well-needed jobs away from able-bodied Americans. On the other hand, there are still those that believe that the jobs being taken away are not ones that Americans would perform due to the terrible working conditions, low pay, and lack of medical coverage. The immigration problem has come to a point where the United States must make a decision to spend a lot of money to curtail the amount of immigrants using force and funds of an overbearing amount, or to just let the immigrants continue to go about their business in trying to find a way into a country where they are mildly welcome. The article 'The Labor Debate'; discusses both the pros and cons of immigrants, both legal and illegal alike, taking jobs of their own in a country where they might not be welcome. I believe that the immigrants are not necessarily taking jobs away from the American worker. Those occupations that the immigrants possess are truly illegal for any employer to employ any American. The job sites include unsanitary conditions, dangerous equipment use without proper safety precautions, extremely long working days, and less than minimum wage for average pay. There is not one citizen in this country that would stand for such an outrageous environment to work in. Many...

Words: 714 - Pages: 3

Free Essay

Tech and Management Functions

... The ranks have swelled and depleted several times over this time period. And after 2005 when the market hit an all-time low, soldiers across all branches decided to stay in, instead of doing the typical four year contract and getting out. During the recruiting process applicants are contacted by phone call, face to face, or a casual meet and greet. Most, honestly join because they have heard from someone the year prior that enlisted and is enjoying the freedom of being out of their parents’ house and being on their own. The recruiting process has many checks and balances that are tracked on line. Everything from how many phone calls we make an hour to the email campaigns we send out every Wednesday morning. Hourly updates are relayed to the station commander who puts together spread sheets daily and reports on those spread sheets at the end of every recruiting day. From appointment start the paper trail is begun. The recruiter is tasked to build the lead into the system. Virtually taking as much information they can from the applicant, and building the packet based on that. The lead process website is massive and can hold as many leads as needed. Just one school in my old office had 5 thousand students revolving in and out yearly. This was one out of twenty one schools in our foot print, that needed 100% contact with in the first four months of the school year. When the applicant steps into the office for the appointment, the recruiter is sizing them up for height and weight...

Words: 1043 - Pages: 5

Free Essay

Reporting Bad News; Whose Interests Matter?

...relies on transparency and honesty. Bankruptcy filings are material information and, as such, investors have a right to know that a company is in distress. On the other hand, filing for bankruptcy protection is intended to help the company get out from under debt and keep operating. Disclosure can work against that process. With the introduction of innovations such as credit default swaps, creditors are less likely to be motivated to work with the company. Furthermore, employees with mobility are likely to begin departing once they know the company’s future is in doubt. Investors have a right to know, while stakeholders have a right to their livelihood. Where do we draw the line (9)?” Corporate Bankruptcy Explained Bankruptcy is a judicial process to provide an individual or a business that no longer can pay its debts with relief from financial obligations. It distributes a debtor’s property equitably among creditors and enables the debtor to start afresh. Federal bankruptcy laws govern how companies go out of business or recover from crippling debt. The most common bankruptcies are Chapter 7 liquidations and Chapter 11 reorganizations. Under Chapter 7, the corporation must stop conducting all operations and goes completely out of business. A court appointed trustee liquidates the company’s assets and the money is used to pay off the debt...

Words: 2837 - Pages: 12

Premium Essay

In the Case Study for Carl Robins

...room for the day! For Carl, not following up on any of the process until the last minute was one of his greatest down falls for the moment. To give a better understanding or idea of what is going on. Here is some information about Carl Robins. In the October, Carl started working for ABC Inc. as the new campus recruiter. He shown strong working knowledge of specialty and job, reliably applies knowledge accomplish task, and met the requirements at a timely fashion with no supervision needed. Carl will seek out extra responsibility and try to take on the hardest jobs. Six months later on his first recruitment effort, talented campus recruiter who consistently exceeds expectation. Mr. Robins specifically selected 15 new hires that were to work for the Operation Supervisor, Monica Carrolls. Carl was to gather and organize all the information from the new trainees and planned to start the orientation for the new hire on June 15 in the training room. To Carl getting all of the requirements for the trainees processes from the beginning of April to June 15, will be more than enough time to get...

Words: 1336 - Pages: 6

Premium Essay

Interpersonal Effectiveness

...M5A2 Reflective Analysis and Interpersonal Improvement Plan Worksheet Use this worksheet to organize your responses to Module 5, Assignment 2. Submit this worksheet in the Module 5: Assignment 2 Dropbox no later than Day 6 of Module 5. Include vocabulary and concepts from your readings to support and illustrate your own insights. In preparation for the papers you’ll write later in this course, take the time to organize your thoughts for each question and write clearly. The completed worksheet should be not more than three pages. 1. Personal goal: I would like to improve my anger management when faced with a difficult task. • Intermediate Goal 1: Finish my courses in interpersonal effectiveness. o Action item 1: Understand, and put to use, all of what is mentioned in my interpersonal effectiveness classes. o Action item 2: Take positive notes for referencing in the future and answer all homework assignments as completely as possible. • Intermediate Goal 2: Practice Relaxation techniques “A major strategy for modifying a stressor is to rethink your belief about a challenging situation.” (Retrieved from: http://digitalbookshelf.argosy.edu/books/9781256958567/id/pg365) o Action item 1: Take 5 minutes a day to listen to soothing music with eyes closed o Action item 2: Focus on the end goal and realize that stress is only temporary • Intermediate Goal 3: Fully recognize stressful...

Words: 2213 - Pages: 9

Free Essay

Memory Management

...system has to figure out what sections of the memory are free and are being used at the current time allocating and reallocating as needed. Memory management is extremely important in how a computer operates. In this paper, we will compare the new Windows 8 to the Linux operating system and describe the differences in the memory management. Windows 8, it is the newest product in operating systems for Microsoft. With enhancements from the previous version, Windows 8 makes better use of the memory management than the previous version Windows 7. In Windows 7, Microsoft started making changes to the operating system when it came to memory management; however, fell short compared to what was already being done in Linux operating system. With the previous versions, most of the memory management occurred upon login. This slowed the processor down taking up all the resources at one time using the system memory. To address this issue and correct it in Windows 8, Microsoft implemented a start on demand model. What this means is that processes that are needed are delayed until the process is needed verses having all the processes start automatically when the computer is started. This makes more run on scheduled than before which frees up startup memory. According to Microsoft (2013),” Virtual memory combines your computer’s RAM with temporary space on your hard disk. When RAM runs low, virtual memory moves data from RAM to a space called a paging file. Moving data to and from...

Words: 876 - Pages: 4

Premium Essay

Interview

... EHR Software Without being healthy, you can hardly enjoy other things, so Physicians and nurses are here to take care of patients. Therefore, while taking well care of patients, getting paid is also important for health care professionals. In statistics, the entire United States has a great amount of more than 1.7 trillion dollars allocated in health care industry. There are still many areas that in health care industry need to be improved. Medical billing process system is one of the big sections and directly determines the benefits of all roles in health care industry. The traditional of doing medical billing that is still being used by many small practices and physicians is considered time-wasting, low-cost efficiency, and error making to compare with new idea of EHR. Before the idea of EHR came out, when a patient visits a doctor, doctor will record medical procedure that has done to that patient and the patient’s diagnosed health problems on patient encounter. Then, the doctor has to hire someone deliver the patient records to hired medical billing company. After medical billers receive and file the patients’ doctor visits records to insurance, the whole process for a doctor getting paid is almost three or more weeks later after patient’s visit. Excluding other disadvantages, this is how complicate and time wasting the traditional way is. EHR stands for electronic health record is a record in digital...

Words: 564 - Pages: 3