FR 3104349 A1 20210611 FR 1913910 A 20191207 Le procédé de compression de données informatiques numérisées «COMPRESSION-B C P » ( B C P pour Base, Combinaison, Produit ) est un procédé de codage/compression adaptable à tout document informatique, sans perte et de taux théorique de compression infini. En base ( b ), b entier naturel, ce procédé code et compresse le code binaire originel du document par découpage en suites binaires de bits indiquant le nombre des cases de présence d'un bit dit « bit d'étude » et noté « Be ». Ce nombre est noté « NBe ». La compression se continue en 3 phases, suivant les valeurs de NBe : PHASE1 = = > Codage simple des cases du bit d'étude Be. PHASE2 = = > Codage des cases du bit d'étude Be par numéro de combinaisons. PHASE3 = = > Codage des cases du bit d'étude Be par numéro du produit de ces cases, produit décomposé en facteurs premiers. Pour b ≥ 8, chaque suite binaire de bits peut être codée / compressée en une suite binaire inférieure à bits. Plus la base b est grande, plus le gain en bits est important. En particulier : 25% en base 10 ( ordre du kilobit ) 50% en base 20 ( ordre du mégabit ) 75% en base 30 ( ordre du gigabit ) Les cases de présence du bit d'étude Be étant connues, par complémentarité, on en déduit les cases de présence du deuxième bit. Vu le caractère interne du codage ( suite binaire compressée en suite binaire inférieure ) la réitération du procédé peut être effectuée le nombre de fois voulu, d'où le caractère théorique infini de la compression. Le taux théorique de compression tend donc vers l'infini, quand le fichier originel tend vers l'infini. Les calculs de codage font intervenir uniquement des opérations arithmétiques sur les nombres entiers naturels ( compression sans approximation donc sans perte ). Des boîtiers spéciaux de codage / compression doivent découler de l'exploitation de cette méthode de «COMPRESSION-B C P ». Compression Informatique « B C P » La présente invention concerne une méthode de codage et de compression pour des données informatiques. Ce procédé peut porter le nom de « COMPRESSION-B C P » , « B » pour Base, « C » pour Combinaison et « P » pour Produit. Ce procédé de compression informatique remédie aux défauts de méthodes de compression déjà existantes et apporte de réelles innovations. Actuellement il existe de nombreux logiciels de compression informatique plus ou moins efficaces, chacun étant spécialisé dans la compression de certaines formes de documents (Texte, Son, Film, Vidéo, …). La méthode « COMPRESSION-B C P » s'adapte à toutes les formes de documents informatisés. Le procédé de « COMPRESSION-B C P » assure une compression parfaitement sans perte dans tous les cas. Le taux théorique de compression du procédé « COMPRESSION-B C P » est infini, si on prend comme définition du taux de compression le rapport du poids informatique avant compression sur le poids informatique après compression, par suite de la répétition du processus. Le principe général étant de retranscrire une suite binaire de longueur fixe en une suite binaire plus petite (également de longueur fixe), puis répéter le processus, toute quantité de bits peut se compresser en quelques bits, suivant le choix de fin de compression effectué. L'importance de la compression informatique ne peut que croître pour des raisons évidentes d'archivage, conservation de données, transmission, téléchargement de fichiers numérisés. L'intérêt écologique ne peut être également sous-estimé ( baisse très importante de la quantité d'énergie nécessaire au stockage et transport des données informatiques ). La fabrication de boîtiers spéciaux de codage /compression (plus transmission) peut être envisagée. Résumé : « COMPRESSION-B C P » Compression parfaitement sans perte avec un taux de compression infini pour tous documents numérisés. oooooooooooooooooooo Cette demande de brevet apporte de grandes améliorations au certificat d'utilité, déposé en 2014 et accordé en 2016 dont les références détaillées sont indiquées ci-après ( avec Abrégé et Revendications ). La méthode « COMPRESSION-B C P » reprend des résultats énoncés dans ce certificat. En effet, malgré la validité de cette précédente méthode ( méthode « B S P » ), il s'est avéré que la décompression était trop lente pour être exploitable, ceci étant dû à une boucle de tests trop nombreux. En revanche, la compression s'est révélée très rapide. Le procédé de « COMPRESSION-B C P » remédie à ce problème, avec des temps de compression et décompression sensiblement égaux. oooooooooooooooooooo Certificat d'utilité Titulaire(s) : BLANC REMY BERNARD LOUIS COMPRESSION de DONNEES INFORMATIQUES N° et date de publication de la demande FR3028118 - 2016-05-06 (BOPI 2016-18) Type de la demande A3 N° et date de dépôt FR1402489 - 2014-11-04 N° et date de priorité FR1402489 - 2014-11-04 Classification CIB H03M7/30 Classification CPC H03M7/30 Famille de brevets FR3028118A3 L’abrégé était le suivant : La méthode de compression de données informatiques « COMPRESSION-B S P » est une méthode de codage/compression adaptable à tout document informatique, sans perte et de taux théorique de compression infini. En base (b), b entier naturel, elle code et compresse le code binaire originel du document par découpage en tranches de suites binaires de bits, indiquant la somme le produit des cases de présence d'un bit dit "minimum", d'où l'abréviation « B S P » pour base, somme et produit. Pour b ≥ 9, chaque suite binaire de bits est ainsi codée/compressée en une suite binaire de bits. Ces données permettent de déduire en décodage/décompression les cases de présence du « Bit Minimum » donc par complémentarité les cases de présence de l'autre bit soit par concaténations et itérations toute la suite binaire originelle. Vu le caractère interne du codage (suite binaire transformée en suite binaire) les programmes informatiques associés aux bases (b), (Progc;b) (compression) et (Progd;b) (décompression) peuvent être réitérés d'où le caractère théorique infini de la compression. Les calculs de codage font intervenir uniquement des opérations sur les nombres entiers naturels. Des boîtiers spéciaux de codage / compression doivent découler de l'exploitation de cette méthode. Les revendications étaient les suivantes : 1) Procédé pour compresser des fichiers informatiques caractérisé en ce qu'il compresse le code binaire source du fichier numérique à compresser après découpage en suites de bits, appelées « bases b », b nombre entier naturel. 2) Procédé de compression informatique selon la revendication1 caractérisé en ce qu'il compresse une suite binaire de bits, b nombre entier supérieur ou égal à 9, en une autre suite binaire de moitié plus petite soit une suite binaire de bits. 3) Procédé de compression informatique selon l'une quelconque des revendications précédentes caractérisé en ce qu'il compresse tous les fichiers informatiques numérisés sans considération de forme, parfaitement sans perte. 4) Procédé de compression informatique selon l'une quelconque des revendications précédentes caractérisé en ce qu'il compresse tout fichier informatique de poids quelconque (Kilo-Octets) en un fichier de poids pouvant être fixé préalablement (Poids minimum de l'ordre de 50 Ko), ce qui confère un taux de compression théorique de 100% au procédé de compression informatique. 5) Procédé de compression informatique selon l'une quelconque des revendications précédentes caractérisé en ce qu'il compresse une suite binaire de bits, b nombre entier naturel, en étudiant la somme et le produit des cases de présence d'un bit appelé « Bit Minimum ». oooooooooooooooooooo L'étude se présentera en 2 parties. La première partie , « Partie Principale » , présente les bases du procédé de compression informatique « COMPRESSION-B C P » et suffit à démontrer les affirmations précédentes, à savoir : compression parfaitement sans perte avec taux théorique de compression infini. La deuxième partie , « Partie Annexe », apporte des exemples, des compléments, des détails, des remarques de programmation. Page 4 à Page 44 Partie Principale Page 45 à Page 95 Partie Annexe Pages 96-97 Revendications Page 98 Abrégé oooooooooooooooooooo Gain en bits On notera Gb(Ba ; b) le gain en bits en base b. Gb(Ba ; b) sera défini par la différence entre le nombre de bits « AVANT COMPRESSION » et « APRES COMPRESSION ». En base 10, on fixe Gb(Ba ;10) à 256 (bits). On va donc retranscrire une suite binaire de longueur = 1 024 bits en une suite binaire de longueur 756 bits (1024 − 256 = 756). Gb(Ba ;10) = 25 % (256 = 25 / 100 x 1024). Base 10 : COMPRESSION : 1024 bits = = > 756 bits. DECOMPRESSION : 756 bits = = > 1024 bits. Ba se 10 : 1024 bits 756 bits ( 25 % ) Remarque : 256 = et 756 = 512 + 256 = + Ce choix de gain en bits est fait aussi pour faciliter les concaténations de tranches de 1024 bits, pour la compression d'un nombre quelconque de tranches. Il semble évident ,vu que les calculs sont en système binaire, de rester le plus possible dans ce système. Remarques : On verra par la suite que les gains en bits vont croître avec la base. On montrera qu'en bases 20 et 30, les gains en bits pourront être fixés à 50% et 75%. Gb(Ba;20) = 50 % ; Gb(Ba;30) = 75 % . oooooooooooooooooooo A partir de maintenant toutes les définitions, démonstrations, remarques ….. et tous les exemples, calculs seront faits en base 10. oooooooooooooooooooo Cases Une suite binaire de n bits, n entier, peut être représentée par n cases, chaque bit occupant une case. En base 10, ( = 1024 bits ) on aura donc 1024 cases. On choisit de numéroter ces cases classiquement de 1 à 1024. Les cases seront notées : Ci : Ci iéme case avec 1 ≤ i ≤ 1024. Présentation Tableau : Cases C1 C2 C3 C4 …... …... C500 …... …... C1023 C1024 Bits 0 0 1 0 …... …... 1 …... …... 1 1 oooooooooooooooooooo Deuxième Axiome Toute suite binaire est formée uniquement de 2 bits, 0 et 1. On en déduit : Deuxième Axiome : Il suffit de connaître parfaitement le nombre de bits et les positions d'un seul bit pour transcrire parfaitement toute suite binaire. Par complémentarité, on déduit les positions du deuxième bit. Exemple : Soit une suite binaire de 5 bits : { 0 1 1 0 1 }. Si on sait, par exemple, que cette suite est formée de 5 bits et que le premier bit ainsi que le quatrième est 0, on déduit aisément que le bit 1 est en deuxième, troisième et cinquième position d’où la suite { 0 1 1 0 1 }. oooooooooooooooooooo Séquence de codage / compression Soit une suite binaire A. On notera Comp(A) la suite binaire après compression de la suite binaire A. Compression A Comp(A) Décompression En base 10, on considère des suites binaires de longueur 1024 bits qui donneront chacune une séquence de codage / compression de longueur 768 bits ( 1024 − 256 = 768 ). Base10 : Comp(.) 768 bits Les bits de Comp(.) seront notés également de façon classique de Bit1, Bit2 ..... à Bit768. Une plage de bits sera notée : Bitx à Bity. Comp(.) = { Bit1;Bit2;Bit3;Bit4; ..... ;Bit400; ..... ;Bit767;Bit768 } oooooooooooooooooooo On va commencer à étudier la séquence de codage / compression ( 768 bits ) en base 10. On notera simplement « A » la suite binaire de = 1024 bits étudiée. A = { 0 1 0 1 1 …..... ( 1024 bits ) …..... 1 0 1 1 } L'étude sera divisée en 4 phases numérotées de 0 à 3 notées : PHASE0 ; PHASE1 ; PHASE2 ; PHASE3. La PHASE0 est la phase d'initialisation, qui déterminera si la compression doit se poursuivre en PHASE1 ou PHASE2 ou PHASE3. Les 3 premières phases ( 0 ; 1 ; 2 ) sont relativement simples et font appel à des notions classiques. La PHASE3 est un peu plus complexe. oooooooooooooooooooo Rappel de Codage Binaire Soit n un entier : n bits permettent de coder cas ( possibilités ). n bits cas Exemple : n = 2 = = > 2 bits = = > = 4 cas Inversement : Soit p cas à coder. Ceci nécessite n bits tel que : Exemple : p = 40 = = > = 32 = = > n = 6 bits. oooooooooooooooooooo PHASE0 La PHASE0 entraîne le codage de 5 paramètres : le nombre de Bit d'étude (NBe), le Bit d'étude (Be), et la première case C1 ainsi que les dernière et avant-dernière cases C1024 et C1023. On va expliciter en détails ces 5 codages. oooooooooooooooooooo Codage de C1 ; C1023 ; C1024 Soit A une suite binaire ( 1024 bits ). Il suffit de coder la première case C1, l'avant-dernière case C1023 ainsi que la dernière case C1024 de la suite binaire par le bit qui occupe chaque case. Le codage de C1, C1023, C1024 nécessite un seul bit par case soit 3 bits au total. Si bit ( 0 ) en C1, C1023, C1024 coder par 0 Si bit ( 1 ) en C1, C1023, C1024 coder par 1 Intérêt de coder C1 : On rappelle que 1 est élément neutre de la multiplication ( 1 x k = k x 1 = k ) donc après codage, ce cas ne sera plus envisageable ce qui est très important en PHASE3. Intérêt de coder C1024 : 1024 = nécessite 11 bits de codage alors que tout nombre de 2 à 1023 peut être codé sur simplement 10 bits. Ce résultat sera utilisé en PHASE1. Intérêt de coder C1023 : Le choix de C1023 est arbitraire pour obtenir un nombre de cases IMPAIR. Tout autre case aurait pu être choisie. Comme l'on considère des suites de 1024 bits (1024 PAIR) et que 3 cases sont parfaitement connues il ne reste que 1021 cases inconnues (1021 IMPAIR). Ceci facilite en partie le codage en PHASE0, de Be et NBe que l'on va aborder. Remarque : 1021 = 510 + 511 PHASE0 : Codage C1, C1023, C1024 3 Bits dans Comp(.). oooooooooooooooooooo Bit d' étude ( Be ) Les bits des cases C1, C1023, C1024 étant connus, il reste 1021 bits à déterminer dans 1021 cases. Il semble naturel d'étudier le bit qui est le moins présent. Conclusion : Le bit le moins présent peut être dans aucune case ou au maximum dans 510 cases ce qui, au total, représente 511 ( 511 = 510 + 1 ) possibilités. (Rappel : 1021 = 510 + 511). Définition : Le Bit d'étude noté Be est le bit moins présent de la suite binaire considérée. Le nombre de bits d’étude ( Be ) sera noté NBe. On notera Be' le bit complémentaire de Be. Be = 0 Be' = 1 Be = 1 Be' = 0 En base10, NBe peut prendre les valeurs de 0 à 510 soit 511 cas donc NBe se code sur 9 Bits ( = 512 ). Be se code évidemment sur un seul bit. Remarque de codage essentielle : Dans la séquence de compression Comp(.), le codage de NBe sur 9 bits doit impérativement se trouver en début de séquence. En effet, suivant la valeur de NBe, la compression va se poursuivre par les PHASES 1, 2 ou 3. L'ordre des autres paramètres C1, C1023, C1024 et Be sera étudié, de façon définitive, en fin d'étude de compression, en fonction de tous les paramètres connus. Dans un premier temps, on considérera un ordre naturel : NBe; Be; C1, C1023, C1024. PHASE0 : 9 + 1 + 3 = 13 Bits ( 768 – 13 = 755 ) PHASE0 : Comp( ) = { NBe;Be;C1;C1023;C1024; ........755 bits libres….} PHASE0 : Comp( ) = { 9bits ; 1 bit ; 3 bits ; …. 755 bits libres .... } Comp( ) = { PHASE0 ; …... 755 bits libres ...... } ( 768 bits ) oooooooooooooooooooo Résumé : PHASE0 PHASE0 13 bits Comp( ) = { NBe;Be;C1;C1023;C1024; ..... 755 bits libres ..... } Comp( ) = { PHASE0 ; …... 755 bits libres ...... } …. ( 768 bits ) oooooooooooooooooooo PROGRAMMATION de Be et NBe Soit A une suite binaire de 1024 bits dans les cases C1 à C1024. Les cases C1,C1023,C1024 sont codées soit 1021 cases restantes ( 1024 − 3 = 1021 ). On notera : Sb la SOMME des BITS de la case C2 à la case C1022 (1021 cases). On a l' encadrement : 0 ≤ Sb ≤ 1021 La double condition suivante précise Be et NBe : Si 0 ≤ Sb ≤ 510 Alors Be = 1 et NBe = Sb ( Inégalités larges ) Si 510 Remarque : Sb étant la somme de 0 et de 1, Sb est simplement la somme des 1 donc le nombre de bit 1. oooooooooooooooooooo Pour la suite, on supposera que la PHASE0 est terminée donc NBe est connu. On peut aborder l'étude des autres phases. oooooooooooooooooooo PHASE 1 La PHASE1 est opérationnelle pour les 76 valeurs les plus petites de NBe soit 0 ≤ NBe ≤ 75 PHASE1 0 ≤ NBe ≤ 75 La PHASE1 nécessite le résultat très simple suivant : En base b ( bits cases ), pour déterminer parfaitement une case il faut et il suffit de la coder sur b bits, exceptée la case qui nécessite ( b + 1 ) bits. En base 10 ( bits 1024 cases ), une case particulière doit être codée sur 10 bits ( Rappel :, C1024 est déjà codée ). Base 10 : Ck avec 2 ≤ k ≤ 1022 10 bits On sait que, après codage de la PHASE0, il reste 755 bits libres ( 768 – 13 = 755 ). Or 755 = 75 x 10 + 5 donc on peut coder 75 cases, simplement par leur indice. La PHASE 1 s'applique donc uniquement pour : 0 ≤ NBe ≤ 75. Remarque : Il y a 5 bits inutilisés au minimum ( 755 – 750 = 5 ). Ces bits peuvent servir dans des améliorations de codage que l'on verra par la suite. oooooooooooooooooooo Bit neutre ( Bn ) On notera Bn (Bit Neutre) les bits qui n'apportent aucune indication et qui servent uniquement à compléter Comp(.) pour maintenir constante la longueur de cette séquence de compression. On posera : Bn = Bit 0 = 0 Ces bits neutres ne doivent pas être lus. oooooooooooooooooooo Résumé PHASE1 Base 10 = 1024 PHASE1 0 ≤ NBe ≤ 75 Case Ck : 2 ≤ k ≤ 1022 Codage de Ck Codage de k 10 bits Reste au minimum 5 Bits neutres Bn utilisables en amélioration de codage oooooooooooooooooooo L'étude de 2 cas triviaux et un exemple sont donnés par la suite. Cas Triviaux : Page 51 ; Ligne 23 87 à Page 5 4 ; Ligne 25 34 . Exemple PHASE1 : Page 5 4 ; Ligne 25 35 à Page 56 ; Ligne 26 2 3. oooooooooooooooooooo On va aborder la PHASE2, qui comme la PHASE1 va couvrir certaines valeurs de NBe. 76 ≤ NBe ≤ 215. La PHASE2 fait appel aux combinaisons mathématiques (incrémentations informatiques). On va dans un premier temps, rappeler les définitions et propriétés basiques des combinaisons puis exploiter ces propriétés pour la PHASE2 de la « COMPRESSION-B C P » . oooooooooooooooooooo On va uniquement faire les rappels basiques sur les combinaisons, suffisants pour l'étude de la PHASE2. Des approfondissements, utiles suivant la programmation adoptée, seront traités par la suite. oooooooooooooooooooo COMBINAISONS On choisit k objets parmi n objets discernables ( numérotés de 1 à n ) et l’ordre dans lequel les objets sont placés (ou énumérés) n’a pas d’importance. On peut les représenter par un ensemble à k éléments. Exemple : Main qu'on obtient en tirant simultanément k cartes dans un jeu de n cartes. Main de bridge :13 cartes dans un jeu de 52 cartes ( k = 13 ; n = 52 ). Définition : Soit E un ensemble fini de cardinal n et k un entier naturel. Les combinaisons de cet ensemble sont ses sous-ensembles (ou ses parties). Une k-combinaison sans répétitions de E, combinaison sans répétitions de n éléments pris k à k, est une partie à k éléments de E. On peut noter: Pk( E ) l’ensemble des k-combinaisons de E. Factorielle : Définition : Soit n un entier naturel. n ≥ 0 On note n! et on lit « factorielle de n » le produit des n entiers consécutifs de 1 à n. n! = = 1 x 2 x 3 x ……. x (n-1) x n ; On pose 0! = 1 Exemples : 1! = 1 ; 2! = 2 x 1 = 2 ; 3! = 3 x 2 x 1 = 6 10! = = 10 x 9 x 8 x .... x 2 x 1 = 3 628 800 Remarque : La croissance « factorielle » est extrêmement rapide. Nombre de combinaisons : k et n entiers ; k ≤ n. L’ensemble Pk( E ) est fini et son cardinal sera noté C( k ; n ) . C( k ; n ) = Nombre de combinaisons de k éléments dans n. On a la formule classique : C( k ; n ) = n ! / k ! x ( n − k ) ! soit C( k ; n ) = . Exemple : E = ( a ;b ;c ;d ;e ) 5 lettres ; Card(E) = n = 5 ; k = 2 Le nombre de couples de 2 lettres prises dans E est : C(2;5) = = = = 5 x 2 = 10 En effet : (ab) (ac) (ad) (ae) (bc) (bd) (be) (cd) (ce) (de) 10 couples. Formule de calcul simplifiée : C( k ; n ) = = Exemple : C(3;6) = = 5 x 4 = 20 Propriétés des combinaisons : Valeurs particulières : C( 0 ; n ) = C( n ; n ) = n! / n! = 1 C( 1 ; n ) = C( n−1; n ) = n! / ( n – 1 )! = n Symétrie : C( k ; n ) = C( n − k ; n ) avec : k + ( n – k ) = n Exemple : C( 2 ; 5 ) = 5! / 2! x 3! = 5! / 3! x 2! = C(3;5) = 10 ( 2 + ( 5 – 2 ) = 5 ) Formule de récurrence : C( k ; n ) = C ( k ; n − 1 ) + C( k − 1 ; n − 1 ) Exemple : C(3;10) = 10! / 3! x 7! = = 10 x 4 x 3 = 120 C(3;9) = 9! / 3! x 6! = = 4 x 3 x 7 = 84 C(2;9) = 9! / 3! x 7! = = 9 x 4 = 36 C(3;9) + C(2;9) = 84 + 36 = 120 = C(3;10) Formule de la somme des combinaisons : = Exemple : = C(0;5)+C(1;5)+C(2;5)+C(3;5)+C(4;5)+C(5;5) = 1+5+10+10+5+1 = 32 = Résultat : Maximum : Soit Card(E) = n. Le MAXIMUM, en combinaison dans n, est atteint pour : k = n / 2 si n est pair k = ( n − 1 ) / 2 et k = ( n + 1 ) / 2 si n est impair Exemples : n = 10 = = > n pair = = > n / 2 = 10 / 2 = 5 et Max = C(5;10) = 252 n = 11 = = > n impair = = > ( n − 1) / 2 = 10 / 2 = 5 et (n+1) / 2 = 12 / 2 = 6 Max = C(5;11) = C(6;11) = 462 Compléments : ( Voir Annexe ) : Page 90; Ligne 4288 à Page 92 ; Ligne 4375. oooooooooooooooooooo Approche de la PHASE2 On va voir 2 exemples très simples de l'utilité de se servir des combinaisons. On a vu qu'en base10, après la PHASE0, il reste 1021cases à déterminer. Exemple1 : Soient 2 cases Cx et Cy à déterminer parmi les 1021 cases. On peut les coder suivant le principe de la PHASE1 c'est à dire les coder chacune sur10 bits ce qui nécessite 2 x 10 = 20 bits pour les 2 cases. On peut aussi numéroter toutes les combinaisons possibles de 2 cases prises dans1021 cases, l'ordre de numérotation étant constant. Le couple (Cx;Cy) peut être déterminé par son numéro de combinaison qu'on peut noter : N°(Cx;Cy). Or le nombre de combinaisons possibles de 2 cases dans 1021 est : C(2;1021). C(2;1021) = 1021! / 2! x 1019! = = 1021 x 510 = 520 710 On a l'encadrement suivant : 262 144 = = 524 288 Conclusion : Le numéro de combinaison cherché N°(Cx;Cy) peut se coder sur uniquement 19 bits. On constate le gain d'un bit par rapport à la PHASE1 (19 bits au lieu de 20 bits). L'ordre des combinaisons étant fixé, le numéro de la combinaison N°(Cx;Cy) permet de retrouver les cases Cx et Cy. Exemple2 : Soient 10 cases C1; C2; ..... ; C10 à déterminer parmi les 1021 cases. Un codage du type de la PHASE1 nécessite 10 x 10 = 100 bits Le nombre de combinaisons possibles de 10 cases dans 1021 est : C(10;1021). C(10;1021) = 1021! / 10! x 1011! = = 324 558 852 305 162 719 481 666 ≈ 3,25 x On a l'encadrement suivant : 3,02 x ≈ ≤ ≈ 6,04 x . Conclusion : Le numéro de combinaison cherché N°(C1;C2;....;C10) peut se coder sur uniquement 79 bits au lieu de 100 bits par la méthode directe de codage des cases de la PHASE1 soit un gain de 21 bits. Résultat : On va exploiter ce gain en bits de codage par la méthode des combinaisons en PHASE2 tant que le nombre de bits d'étude NBe le permet. oooooooooooooooooooo Avant d'aborder la PHASE2 de la « COMPRESSION-B C P » on va voir sur un exemple très simple d'une numérotation par combinaison. Exemple : Soient les 6 entiers consécutifs { 1;2;3;4;5;6 } On veut numéroter les triplets possibles. On sait donc que l'on cherche 3 nombres (3 est fixé connu) dans 6 nombres possibles, nombres fixés et connus. Au total il y a C(3;6) cas possibles avec C(3;6) = 6! / 3! x 3! = = 5 x 4 = 20 On numérote tous les cas possibles de 1 à 20. On pose naturellement : N°1 ( 1;2;3 ) Puis on incrémente de ( +1 ) tant que possible : Limite 6 pour le troisième nombre, limite 5 pour le deuxième nombre, limite 4 pour le premier. Ceci fixe l'ordre des incrémentations donc de la numérotation. Différents ordres d'incrémentations peuvent être envisagés. ( 1;2 ) Fixé = = > Incrémentations de (+1) sur 3 N°1 ( 1;2;3 ) ; N°2 ( 1;2;4 ) ; N°2 ( 1;2;5 ) ; N°4 ( 1;2;6 ) ( 1;3 ) Fixé = = > Incrémentations de (+1) sur 4 N°5 ( 1;3;4 ) ; N°6 ( 1;3;5 ) ; N°7 ( 1;3;6 ) ( 1;4 ) Fixé = = > Incrémentations de (+1) sur 5 N°8 ( 1;4;5 ) ; N°9 ( 1;4;6 ) ( 1;5 ) Fixé = = > Incrémentations de (+1) sur 6 N°10 ( 1;5;6 ) = = > FIN ( avec premier nombre = 1 ) ( 2;3 ) Fixé = = > Incrémentations de (+1) sur 4 N°11 ( 2;3;4 ) ; N°12 ( 2;3;5 ) ; N°13 ( 2;3;6 ) ( 2;4 ) Fixé = = > Incrémentations de (+1) sur 5 N°14 ( 2;4;5 ) ; N°15 ( 2;4;6 ) ( 2;5 ) Fixé = = > Incrémentations de (+1) sur 6 N°16 ( 2;5;6 ) = = > FIN ( avec premier nombre = 2 ) ( 3;4 ) Fixé = = > Incrémentations de (+1) sur 5 N°17 ( 3;4;5 ) ; N°18 ( 3;4;6 ) ( 3;5 ) Fixé = = > Incrémentations de (+1) sur 6 N°19 ( 3;5;6) = = > FIN ( avec premier nombre = 3 ) ( 4;5 ) Fixé = = > Incrémentations de (+1) sur N°20 ( 4;5;6 ) = = > FIN Conclusion : Explications succinctes : Pour ne pas trop alourdir la lecture, on va faire quelques remarques calculatoires simplifiées qui seront approfondies par la suite. Pour la PHASE2, il suffit de voir qu’ on peut coder un numéro de combinaison unique et retrouver la combinaison unique à partir de son numéro. On constate ( propriétés des combinaisons ) qu'on a des sommes de sommes décroissantes d'entiers consécutifs à partir de 4. A partir de la combinaison N°1 ( 1;2;3 ) , le nombre de valeurs possibles pour le troisième nombre du triplet est 4. 3 = = > 3;4;5;6 = = > 4 valeurs possibles et 4 = ( 6 – 3 ) + 1 Chaque somme d'entiers consécutifs décroissante correspond à des sauts de changements de valeurs du premier terme. 20 = (4+3+2+1) + (3+2+1) + (2+1) + (1) = 10 + 6 + 3 + 1 Exemples : N°11 ( 2;3;4 ) 11 = 10 + 1 donc 1 = = > 2 ; 2= = > 3 ; 3= = > 4 N°12 ( 2;3;5 ) 12 = 10 + 2 donc 1 = = > 2 ; 2= = > 3 ; 3= = > 5 On pourra coder en introduisant des notions d'écarts ( Ecart Max = 4 = ( 6 – 3 ) + 1 ). Plusieurs types de programmation sont évidemment envisageables. Approfondissements ( Voir Annexe ) : Page 80 Ligne 3787 à Page 81 Ligne 3877 ). oooooooooooooooooooo On va reprendre en Base10 et conclure avec la PHASE2 en calculant les valeurs possibles de NBe pour lesquels la PHASE 2 sera opérationnelle. oooooooooooooooooooo PHASE2 (suite) On rappelle que la PHASE1 s'applique pour 0 ≤ NBe ≤ 75. La PHASE2 doit donc commencer à NBe = 76. On rappelle qu'après la PHASE0, le nombre de cases inconnues n'est plus que de 1021. Le calcul des valeurs de combinaisons se fera donc sur 1021. On rappelle qu'après la PHASE0, le nombre de Bits libres de codage est 755 ( 768 – 13 = 755 ). Résultat : La valeur de la combinaison C(NBe;1021) ne doit pas excéder . On va donc faire les calculs de combinaisons pour déterminer NBe maximal en PHASE2. Calculs de combinaisons : 1) NBe = 76 = = > C( 76 ;1021 ) ≈ 1,4696 x ≈ 7,880 x ≤ 1,576 x ≈ ( ) et 755 – 386 = 369 PHASE2 : NBe = 76 386 Bits ( 369 bits neutres Bn = 0 ) 2) NBe = 100 = = > C( 100 ;1021 ) ≈ 5,6897164233845 x ≈ 3,810 x ≤ 7,621 x ≈ ( ) et 755 – 468 = 287 PHASE2 : NBe = 100 468 Bits ( 287 bits neutres Bn = 0 ) 3) NBe = 200 = = > C( 200 ;1021 ) ≈ 6,7779492454053 x ≈ 4,412 x ≤ 8,825 x ≈ ( ) et 755 – 724 = 31 PHASE2 : NBe = 200 724 Bits ( 31 bits neutres Bn = 0 ) 4) NBe = 210 = = > C(210 ;1021) ≈ 6,65180265634615 x ≈ 4,626 x ≤ 9,253 x ≈ ( ) et 755 – 744 = 11 PHASE2 : NBe = 210 744 Bits ( 11 bits neutres Bn = 0 ) 5) NBe = 215 = = > C( 215 ;1021 ) ≈ 5,25809578801497 x ≈ 4,737 x ≤ 9,475 x ≈ ( ) et 755 – 754 = 1 PHASE2 : NBe = 215 754 Bits ( 1 bit neutre Bn = 0 ) 6) NBe = 216 = = > C( 216 ;1021 ) ≈ 1,96204870608336 x ≈ 1,895 x ≤ 3,790 x ≈ ( > ) et 755 – 756 PHASE2 : On ne peut pas opérer en PHASE2 pour NBe = 216. Conclusion : La PHASE2 peut s'appliquer pour : 76 ≤ NBe ≤ 215 oooooooooooooooooooo Résumé PHASE2 Base 10 = 1024 PHASE2 76 ≤ NBe ≤ 215 C( NBe;1021 ) Codage de N° C ( NBe;1021 ) N°1{ C(NBe;1021) } 2 ; 3; 4; ......; (NBe-1); NBe Chaque incrémentation de (+1) augmente N°1{ C(NBe;1021) } de 1 Améliorations de codage possibles car 1 ≤ Nombre Bits neutres ≤ 369 oooooooooooooooooooo Un exemple de PHASE2 est explicité en partie annexe. Voir Annexe : Page 57 ; Ligne 2625 à Page 59 ; Ligne 2728. oooooooooooooooooooo On peut traiter 216 cas de valeurs de NBe, 0 ≤ NBe ≤ 215 par les PHASE1 et PHASE2. La PHASE3, va permettre de traiter les derniers cas ( 216 ≤ NBe ≤ 510 ) en imposant une nouvelle contrainte. On va faire, dans un premier temps une approche rapide de la PHASE3 puis dans un deuxième temps les rappels mathématiques nécessaires pour approfondir et formaliser la PHASE3. oooooooooooooooooooo Approche PHASE3 On va introduire dans cette PHASE3 la contrainte (Variable) P que l'on va définir comme le PRODUIT des CASES de PRESENCE de Be, NBe étant connu. Rappel : C1 est déjà codée. On rappelle également que l'on conserve un ordre strictement croissant ,donc sans répétition possible. Connaissant P, on peut numéroter tous les produits possibles, comme en PHASE2 avec les combinaisons. Exemple simple en décimal : NBe = 4 et Be dans les cases C2; C4; C6; C10. P = C2 x C4 x C6 x C10 = 2 x 4 x 6 x 10 = 480 = × × On sait donc que P = 480 sur 4 Facteurs (cases). Enumération des produits possibles à partir de P1 On pose : P1 = 2 x 3 x 4 x 20 ( = 480 ) On choisira évidemment un ordre constant de construction. N°(P) = 1 = N°1 P1 = 2 x 3 x 4 x 20 ( = 480 ) N°(P) = 2 = N°2 P2 = 2 x 3 x 5 x 16 ( = 480 ) N°(P) = 3 = N°3 P3 = 2 x 3 x 8 x 10 ( = 480 ) N°(P) = 4 = N°4 P4 = 2 x 4 x 5 x 12 ( = 480 ) N°(P) = 5 = N°5 P5 = 2 x4 x 6 x 10 ( = 480 ) N°(P) = 6 = N°6 P6 = 2 x 5 x 6 x 8 ( = 480 ) N°(P) = 7 = N°7 P7 = 3 x 4 x 5 x 8 ( = 480 ) Remarques : 3 x 4 x 5 x 10 = 600 > 480 donc P7 est le dernier produit possible. 4 x 4 x 5 x 6 = 480 Impossible car répétition de 4. Conclusion : Le produit des cases voulues est donc : P5. Inversement si on connait ( P = 480 ; N°(P) = 5 ; N = 4 ) ,il est possible de retrouver les 4 cases originelles N = 4 et P = 480 = = > P1 = 2 x 3 x 4 x 20 ( = 480 ) N°(P) = 5 = = > P5 =2 x 4 x 6 x 10 ( = 480 ) = = > Cases C2; C4; C6; C10 . oooooooooooooooooooo Il reste à montrer que le couple (P ; N°(P)) peut se coder avec un nombre de bits qui vérifie les conditions de compression initiale prévue pour 216 ≤ NBe ≤ 510. On va donc faire l'étude en BASE10 par codage du produit des cases de Be et d’un numéro qui spécifiera ce produit. On va, dans un premier temps voir l'étude et le codage d'un produit P. Des rappels mathématiques d'arithmétique sont nécessaires. Les calculs et formules applicables vont se faire principalement, non en décimal mais sur la forme de décomposition en facteurs premiers. oooooooooooooooooooo NOMBRES PREMIERS Définition d'un nombre premier : Un nombre premier (abréviation NP ) est un nombre entier qui ne possède que deux diviseurs, 1et lui-même. Exemples : 11 (1 x 11 = 11 uniquement) est premier et 12 n'est pas premier car 12 = 3 × 4 = 2 × 6 = 1 × 12. Propriétés de l'ensemble des nombres premiers noté E(NP) : E(NP) est un ensemble infini, ordonné et dénombrable. E(NP) = { 2; 3; 5; 7; 11; 13 ; ......... }. Théorème fondamental sur les nombres premiers : Tout nombre entier naturel est décomposable de manière unique en un produit de puissances de nombres premiers. Pour tout entier n, il existe i entier, ( ) premiers et (ei) entiers tels que : n = × × ….. × = . Exemple : 2100 = × × × . Numérotation des nombres premiers : E(NP) est un ensemble dénombrable donc on peut classer les nombres premiers dans l'ordre croissant et les numéroter sur l'ensemble N *. On notera : = 2 ; = 3 ; = 5 ; = 7 ; ….. ; = 1021 ; ….. oooooooooooooooooooo Croissance d'un produit : La croissance d'un produit est extrêmement rapide. Pour exemple : 50! est de l'ordre de : 3 x ; 100! est de l'ordre de : 9 x . Un codage par valeur décimale nécessiterait donc un trop grand nombre de bits d'où le codage sur les exposants des nombres premiers de la décomposition. On va faire quelques rappels basiques sur les puissances des nombres entiers. oooooooooooooooooooo PUISSANCES Définition : Soient a et n deux entiers: on appelle puissance de base ( a ) et d'exposant ( n ) que l'on note le produit de a par a, n fois. = a × a × a × ….. × a × a ( n fois ). On pose = 1. Remarque essentielle : Si on connaît la base (a), l'exposant seul définit parfaitement la puissance. Propriétés : L'opération « Puissance » est un morphisme de groupe du groupe multiplicatif sur le groupe additif ce qui se traduit par les relations. Soient 4 entiers a, b, m, n : a ) × = Exemple : × = = b ) = Exemple : = = c ) = 1 / a Exemple : = 1 / 2 d ) = 1 / Exemple : = 1 / e ) = / Exemple : = = / f ) = × Exemple : = = × oooooooooooooooooooo Principe de Codage d'un Produit Soit Nn un ensemble de n entiers supérieurs égaux à 2. Nn = { a1; a2; a3; .....; ai; ...... ; an } avec ai ≥ 2 ; 1 ≤ ≤ n On suppose que les décompositions en produit de facteurs premiers sont connues pour chaque ai (Table de décomposition en NP). Tous les produits P d'entiers pris (une seule fois) dans Nn peut s'exprimer comme un produit de puissances de k nombres premiers, par les formules sur les puissances. Il existe k nombres premiers NPi et k exposant ei tels que : P = x x x .......... x = Les n entiers ai étant connus, on connait le nombre et les nombres premiers nécessaires et suffisants pour déterminer tout produit P. Il suffit donc de coder les k exposants ei pour connaître parfaitement P. Pour mieux visualiser on va donner des exemples simples. oooooooooooooooooooo Exemples de codage de produit n = 7 et N7 = { 2; 3; 4; 5; 6; 7; 8 } 4 NP sont inférieurs égaux à 8 : ENP = { 2; 3; 5; 7 } On dresse la table de décomposition en NP. ai Décomposition en NP NP1 e1 NP2 e2 NP3 e3 NP4 e4 2 2 1 3 0 5 0 7 0 3 2 0 3 1 5 0 7 0 4 2 2 3 0 5 0 7 0 5 2 0 3 0 5 1 7 0 6 x 2 1 3 1 5 0 7 0 7 2 0 3 0 5 0 7 1 8 2 3 3 0 5 0 7 0 Exemples de produit : 1) P1 = 2 x 4 x 5 = 40 = x x x Il sera impératif de coder les exposants de TOUS les NP possibles, pour garder la continuité de codage. L'exposant 0 ( = 1 ) doit être décompté. L'exposant 0 correspond au cas où le NP considéré n'est pas dans la décomposition. Par la table de décomposition, les exposants des NP sont aisément calculables en faisant les sommes sur toutes les colonnes exposant ,et uniquement sur les lignes des NP nécessaires. 2) P2= 2 x 3 x 5 x 7 = 210 = x x x Exp(2) = 1 Exp(3) = 1 Exp(5) = 1 Exp(7) = 1 3) P3 = 8! = 2 x 3 x 4 x 5 x 6 x 7 x 8 = 40 320 = x x x Exp(2) = 7 Exp(3) = 2 Exp(5) = 1 Exp(7) = 1 Remarque sur P3 = 8! : Le calcul précédent permet d'avoir les exposants maximaux de chaque NP donc le nombre de bits nécessaires au codage de tous les NP donc le nombre de bits nécessaires au codage de tout produit P. Exp,max(2) = 7 + exp(0) = = > 7+1= 8 cas possibles = = > 3 bits Exp,max(3) = 2 + exp(0) = = > 2+1= 3 cas possibles = = > 2 bits Exp,max(5) = 1 + exp(0) = = > 1+1= 2 cas possibles = = > 1 bit Exp,max(7) = 1 + exp(0) = = > 1+1= 2 cas possibles = = > 1 bit Tout produit P se coderait donc sur 7 bits ( 3 + 2 + 1 + 1 = 7 ) Remarque : En décimal, 8! = 5040 devrait se coder sur 13 bits. oooooooooooooooooooo On va approfondir l'étude du codage du produit en base 10. oooooooooooooooooooo BASE10 Codage du produit BASE10 = = > = 1024 = = > { C1;C2;C3;......;C500; ...... ;C1023;C1024 } On tiendra compte uniquement du fait que la case C1 est codée (PHASE0) pour supprimer l'indice 1, élément neutre de la multiplication ( 1 x a = a x 1 = a ) ce qui apporterait trop d'ambiguïtés. L'ensemble des cases à considérer est donc les 1023 cases : {C2;C3;....;C500;....;C1023;C1024} soit la suite des 1023 indices entiers : N1023 = { 2;3; ...... ;500; ...... ;1023;1024 } On suppose que toutes les décompositions en facteurs premiers des entiers de N1023 sont connues. Un extrait de table de décomposition est en Annexe. ( Voir Annexe : Page 45 ) Résultat : En base (10), il existe 172 nombres premiers inférieurs à 1024. E(NP) = { 2 ; 3 ; 5 ; 7; …. ; 1013 ; 1019 ; 1021 }. Ces nombres premiers sont numérotés de 1 à 172 : = 2 ; = 3 ; = 5 ; ….. ; = 1019 ; ….. ; = 1021. E(NP) = { NP1= 2 ;NP1=3 ; NP1=5 ; NP1=7; …. ;NP1=1019 ;NP1=1021 } ; 1 ≤ i ≤ 172. L'exposant du nombre premier de rang i, NPi sera noté ei. On notera max pour Maximum donc emax;i le maximum de ei pour NPi donné. Chaque NP ne sera pas codé sur le même nombre de bits d'où la nécessité de les coder tous dans un même ordre constant. oooooooooooooooooooo On va d'abord étudier une relation mathématique nécessaire au codage du produit. oooooooooooooooooooo Partie entière d'un nombre réel Nombre de multiples Exposant dans P On appelle partie entière d'un nombre réel x notée E(x) le nombre entier tel que : E(x) ≤ x Exemples : E( 3,14 ) = 3 ; E( 3 ) = 3 ; E( 2,9999 ) = 2. Nombre de multiples d'un nombre entier : Soient A et a deux entiers avec A ≥ a. Le nombre de multiples de a inférieur ou égal à A est égal à E( ). Exemple : A = 20 ; a = 3 ; E( ) = E( ) = E( 6,66 ) = 6 On a 6 multiples de 3 inférieurs égaux à 20 : { 3; 6; 9; 12; 15; 18 } On peut faire de même avec = = 9 E( ) = E( ) = E( 2,22 ) = 2 On a 2 multiples de 9 inférieurs égaux à 20 : { 9; 18 } Le calcul est inutile pour = = 27 > 20 Dans un produit P de multiples de 3, l'exposant maximal de 3 serait donc : 6 + 2 = 8 Vérification : Produit des multiples de 3 ( ≤ 20 ) produit { 3; 6; 9; 12; 15; 18 } 3 x 6 x 9 x 12 x 15 x 18 = x ( x ) x x ( x ) x ( x ) x ( x ) = x x x x x x ( x x x ) = x ( x ) = x ( x ) Vérification : 3 x 6 x 9 x 12 x 15 x 18 = 524 880 x ( x ) = 6561 x 16 x 5 = 524 880 Dans cet exemple on a donc emax(3) = 8 soit 0 ≤ e ≤ 8 donc 9 ( 8 + 1 ) cas possibles ( ne pas oublier le cas 0 ). On en déduirait le nombre de 4 bits nécessaires pour coder le NP 3. 8 Formule de calcul de emax du produit de multiples d'un entier : Soient A, a, p trois entiers tels que A ≥ a ; ≤ A et > A. Alors, dans le produit de tous les multiples de ( a ) inférieurs ou égal à A on a le facteur ( ), l'exposant (e) valant la somme des parties entières des rapports de A sur {a , , , - - - - , }. Produit des multiples de a ≤ A = = > avec : emax = E( A / a ) + E( A / ) + E( A / ) + …. + E(A / ). Formule à retenir : Soit un nombre premier NPi . Soit A un entier ( borne majorante ). Soient ai, n entiers, ai ≤ A. Soit P = le produit de k entiers pris dans { ai } Alors dans P, NPi est à l'exposant ei avec 0 ≤ ei ≤ eimax tel que : eimax = E( A / NPi ) + E( A / ) +E ( A / ) + …. + E (A / ) = eimax donne le nombre de bits nécessaires de codage d'un nombre premier NPi dans un produit. oooooooooooooooooooo On va appliquer cette méthode dans le cas de la Base 10 pour un cas particulier. On en déduira le tableau récapitulatif du produit P en base 10 et le codage de P en termes de bits. Ceci permettra l'étude du numéro du produit pour conclure. oooooooooooooooooooo Exemple Codage NP dans P D'autres exemples seront donnés par la suite. ( Voir Annexe : Page 75 ; Ligne 3572 à Page 76 ; Ligne 3634 ). On va étudier, pour exemple le codage du nombre premier NP5 = 11, dans les conditions de la Base10. Rappel : On considère uniquement les cases de C2 à C1024 donc l'ensemble des indices de 2 à 1024. Etude de NP5 = 11 dans un produit : L'exposant de NP5 = 11 sera noté : e5 = e(11) 1) 11 est dans aucune case = = > e5 = e(11) = 0 Dans les décompositions des cases, NP5 = 11 peut se trouver uniquement à l'exposant 1 ou l'exposant 2. En effet : = 121 ≤ 1024 et = 1331 > 1024. Il suffit de déterminer l'exposant maximal emax;nnnnnNP5 (emax(11)) possible dans le produit. On applique la formule : emax = E( A / NP ) + E( A / ) + E( A / ) + …. + E( A / ) avec A = 1024 ; NP = 11 ; p = 2. emax (NP5) = emax(11) = E( 1024 / 11 ) + E( 1024 / ) = E( 1024 / 11 ) + E( 1024 / 121 ) = E( 93,09) + E( 8,46) = 93 + 8 = 101 On a donc emax;11 = 101 soit 0 ≤ e ≤ 101 donc 102 cas possibles ( 101 + 1 ). On en déduit le nombre de 7 bits nécessaires pour coder NP5 = 11. 64 Exemples : Si on considère toutes les cases multiples de 11 on aura P = x K et on devra coder 101 sur 7 bits. 101 1100101 Si on considère seulement 2 cases multiples de 11, par exemple C11 et C22, on aura P = x K et on devra coder 2 sur 7 bits. 2 0000010 oooooooooooooooooooo Par répétition u processus, on en déduit le nombre de bits de codage de chacun des 172 Nombres Premiers ( Base10 ) donc le nombre de bits total pour le codage du produit. oooooooooooooooooooo Base10 Tableau Récapitulatif du Produit Ordre des Nombres Premiers Valeurs des Nombres Premiers Exposant Maximal Décomposition Exposant Maximal Produit Nombre de Cas Nombre de bits Codage Binaire Nombre de Nombres Premiers 2 10 1 023 1 024 10 1 3 6 508 509 9 1 5 4 253 254 8 1 7 3 168 169 8 1 11 2 101 102 7 1 13 2 84 85 7 1 à 17 --> 31 2 63 --> 34 64 --> 35 6 5 à 37 --> 61 1 27 --> 16 28 --> 17 5 7 à 67 --> 127 1 15 --> 8 16 --> 9 4 13 à 131 --> 251 1 7 --> 4 8 --> 5 3 23 à 257 --> 509 1 3 --> 2 4 --> 3 2 43 à 521-->1021 1 1 2 1 75 Total Bits 396 On notera Nb(P) le nombre de bits nécessaire au codage de TOUT produit P. Nb(P) = (1× 10)+(1× 9)+(2 × 8)+(2 ×7)+(5 × 6)+(7 × 5)+(13× 4)+(23 × 3)+(43× 2)+(75× 1) = 10 + 9 + 16 + 14 + 30 + 35 + 52 + 69 + 86 + 75 = 396. Base10 : Nb( P ) = 396 oooooooooooooooooooo Remarque essentielle sur le codage du produit TOUT NP doit être codé (sur son nombre de bits), même si ce NP n'est jamais présent. Exemple : Si dans P on a que des indices entiers impairs ( cases impaires ), on aura aucun multiple de 2 donc = 1 d'où le codage de 0 sur 10 bits par 0000000000. Ceci permet de conserver la continuité de lecture du codage de P. oooooooooooooooooooo On va affiner le codage de la PHASE3 en remarquant 2 propriétés du codage de P pour pouvoir mettre en place le codage du numéro de P. oooooooooooooooooooo Première propriété du codage de P NP Supérieurs On constate que 75 nombres premiers de NP98 = 521 à NP172 = 1021se codent chacun sur 1 bit. En effet : 2 x 521 = 1042 > 1024 et 2 x NPi > 1024 pour 98 ≤ i ≤ 172. Ceci signifie que l'on sait parfaitement si le Bit d'étude Be est présent (codage 1) ou non présent ( codage 0 ) dans les 75 cases numérotées par ces nombres premiers. Ces 75 NP seront appelés « Nombres Premiers Supérieurs ». Par mesure de simplification il semble naturel de coder directement ces cases, ce qui revient à les supprimer de l'étude du produit. Remarque : Il y a équivalence de bits c'est à dire que l'on peut garder le fait que P se code sur 396 bits sans les NP supérieurs ( donc les cases dites supérieures ). Ceci va permettre de simplifier le produit P et le nombre de cases d'étude. Ces cases supérieures seront codées comme en PHASE0 par le bit qui les occupe. Enumération des 75 Cases Supérieures (NP supérieurs) en Base10 : (75 Case Sup) {521;523;541;547;557;563;569;571;577;587;593;599;601;607;613;617;619;631;641;643;647;653;659;661;673;677;683;691;701;709;719;727;733;739;743;751;757;761;769;773;787;797;809;811;821;823;827;829;839;853;857;859;863;877;881;883;887;907;911;919;929;937;941; 947;953;967;971;977;983;991;997;1009;1013;1019;1021} oooooooooooooooooooo Deuxième propriété du codage de P NP Semi-Supérieurs On peut faire de même pour certains NP qui se codent sur 2 bits. Exemple : Soit NP97 = 509 qui se code sur 2 bits 2 x 509 = 1018 1024 En effet on a 4 cas et uniquement 4 cas possibles pour NP97 = 509. = = 4 Cas1 : ni case 509 ; ni case 1018 Cas2 : case 509 uniquement Cas3 : case 1018 uniquement Cas4 : case 509 et case 1018 En revanche on n'a pas cette propriété pour NP68 = 337 qui se code aussi sur 2 bits. En effet : 2 x 337 = 674 = = 8 donc 8 cas possibles qui ne peuvent se coder sur 2 bits. Conclusion : On codera, comme en PHASE0 par le bit qui les occupe, 58 cases appelées Cases Semi-Supérieures pour les 29NP Semi-Supérieurs de NP69 = 347 à NP97 = 509 et pour les 29 cases doubles de ces 29 NP. Enumération des 58 Cases Semi-Supérieures ( NP Semi-Supérieurs ) : NP Semi-Supérieurs = {347;349;353;359;367;373;.379;383;389;397;401;409;419;421;431; 443;439;443;.449;457; 461;463;467;479;487;491:499;503;509 } 58 Cases Semi-Supérieures : { 347;349;353;359;367;373;.379;383;389;397;401;409;419;421;431;443;439;443;.449;457; 461;463;467;479;487;491:499;503;509;694;698;706;718;734:746;758;766;778;794;802; 818;838;842;862;866;878;886;898;914;922;926;934;958;974;982;998;1006;1018 } Total cases supérieures et semi-supérieures : 133 ( 75 + 58 = 133 ) oooooooooooooooooooo Résultat essentiel en PHASE3 On a 133 cases supérieures et semi-supérieures ( 75 + 58 = 133 ). On réservera donc 133 bits pour coder ces 133 cases. L'étude va donc se porter (en PHASE3) sur 888 cases ( 1021 − 133 = 888 ) Remarque : 888 est Pair Or on va devoir introduire un nouveau bit d'étude, spécial Phase3 noté Be;ph3 et un nouveau nombre de Bit d'étude noté NBe;ph3. Vu l'élimination de 133 cases (plus de 10%) dans l'étude, suivant les cas, il n'est pas du tout obligatoire que Be et NBe de la PHASE0 soient conservés. Pour se rapprocher de la PHASE0; on va coder une case supplémentaire pour avoir un nombre total de cases d'étude impair. La case C512 sera codée par le bit qui l'occupe ( Idem PHASE0 ). En base 10, on va choisir la case C512 sachant que = 512 Or 2 x 512 = 1024 et C1024 déjà codée donc on peut en déduire que NP1 = 2 sera au maximum égal à 8 dans la décomposition des cases. Remarque : Une autre case d'imparité peut évidemment être choisie (ceci dépendant de la programmation utilisée). L'étude va donc se porter ( en PHASE3 ) sur 887 cases ( 888 – 1 = 887 ) PHASE3 887 cases ( non codées ) oooooooooooooooooooo PHASE3 Mise au point et récapitulatif après étude du codage du produit P Après La PHASE0 les cases C1;C1023;C1024 sont codées. Il reste 1021 cases (1024 – 3 = 1021). La PHASE3 est appelée pour NBe tel que : 216 ≤ NBe ≤ 510. Le codage de NBe reste inchangé. En PHASE3, 134 bits sont réservés pour coder 134 cases (cases supérieures, cases semi-supérieures et cases d'imparité). On appellera cet ensemble de cases codées en PHASE3 : CCph3 ( 134 cases). On notera donc leur nombre en base 10 :NCCph3 = 134 L'étude porte sur N887 cases. Remarque : les 887 cases ne sont plus consécutives. Le produit P se codera sur 262 bits (396 – 134 = 262) sur 68 NP de NP1 = 2 à NP68 = 337. Résumé PHASE3 : ( suite à étude du produit P ) 134 cases codées : NCCph3 = 134 N887 cases d'étude 262 bits codage de P 68 NP dans P oooooooooooooooooooo NBe;ph3 et Be;ph3 Le Nombre de Bits d'étude ( NBe ) en PHASE0 permet de diriger vers la PHASE(1;2;3) de compression. Si 216 ≤ NBe ≤ 510 , la compression est dirigée vers la PHASE3 (avec codage du produit P). Au vu de toutes les cases supplémentaires (CCph3) codées, il est nécessaire d'introduire un nouveau bit d'étude Be que l'on notera Be;ph3 et un nouveau nombre de bit d'étude que l'on notera NBe;ph3 . On adaptera la méthode en PHASE0 aux conditions de la PHASE3. oooooooooooooooooooo Recherche de NBe;ph3 et Be;ph3 Il reste 887 cases ( N887 ). 887 / 2 = 443,5 = = > Répartition : 887 = 443 + 444 On va donc choisir : 0 ≤ NBe;ph3 ≤ 443. On considère la somme des bits sur N887 que l'on note Sb;ph3. D'où la conditionnelle : Si Sb;ph3 ≤ 443 alors Be;ph3 = 1 et NBe;ph3 = Sb;ph3 Si Sb;ph3 > 443 alors Be;ph3 = 0 et NBe;ph3 = 887 − Sb:ph3 Ce codage nécessite donc 10 bits (9 + 1 = 10). 0 ≤ NBe;ph3 ≤ 443 = = > 256 ≤ 443 ≤ 512 = = > = = > Codage sur 9 bits Be;ph3 = 0 ou 1 = = > Codage sur 1 bit Codage (NBe;ph3; Be;ph3) 10 bits oooooooooooooooooooo Numéro du PRODUIT Il suffit maintenant de coder le Numéro du produit On va avoir besoin de notions sur les diviseurs d'un nombre. On va donc aborder les propriétés des diviseurs. oooooooooooooooooooo DIVISEURS du PRODUIT P On se place dans l'ensemble N* des entiers naturels non nul. N* = { 1;2;3;........... ; 1000 ; ............. } Définition : Soit a un entier de N*. d est un diviseur de a si et seulement s'il existe un entier k tel que d x k = a. Exemple : 2 est un diviseur de 10 car 2 × 5 = 10 ( a = 10 ; d = 2 ; k = 5 ). Cas particulier : 1 a un seul diviseur ( lui-même ) car 1 x 1 = 1 Diviseurs triviaux : Tout entier a strictement supérieur à 1 possède au moins deux diviseurs 1 et a qui sont appelés ses diviseurs triviaux. a > 1 = = > 1 et a diviseurs triviaux Propriété : Si d est un diviseur de a, tout diviseur de d est aussi un diviseur de a (sorte de hiérarchie parmi les diviseurs d'un entier visualisable par un diagramme de HASSE). Nombre de diviseurs : C'est la relation la plus importante pour notre étude. Soit un entier a décomposé en produit de facteurs premiers : Il existe i entier, ( ) premiers et (ei) entiers tels que : a = × …. × . Exemple : 60 = × × . Résultat : Le nombre Ndiv(a) des diviseurs de a est donné par la formule : Ndiv(a) = (e1 +1) x (e2 +1) x ........ x (ei +1) = ; ei exposant de NPi On notera D(a) l'ensemble des diviseurs d de a. Exemple : 60 = × × = = > Ndiv(60) = ( 2 + 1 ) x ( 1 + 1 ) x ( 1 + 1 ) = 3 x 2 x 2 = 12 Vérification : D(60) = { 1;2;3;4;5;6;10;12;15;20;30;60 } = = > Ndiv(60) = 12 On rappelle également la formule de la somme des diviseurs ( qui peut être utile suivant la programmation utilisée ). Sdiv( n )=[( –1)/(NP1 −1)]x[( −1)/(NP2 −1)]x.....x[( −1)/(NPi −1)] Exemple Sdiv(60) = 1+2+3+4+5+6+10+12+15+20+30+60 = 168 Sdiv(60) = [( − 1) / (2 − 1)] x [( − 1) / (3 − 1)] x [( − 1) / (5 − 1)] = ( − 1) / (2 − 1)] x [( − 1) / (3 − 1)] x [( − 1) / (5 − 1)] = [(8 − 1) / (2 − 1)] x [(9 − 1) / (3 − 1)] x [(25 − 1) / (5 − 1)] = (7 / 1) x (8 / 2) x (24 / 4) = 7 x 4 x 6 = 168 Complément : Sans expliciter, il peut être intéressant en programmation, d'exploiter les notions de partition d'Euler, nombres pentagonaux, diagramme de FERRERS,..... oooooooooooooooooooo Partition d'un produit Définition : On dira qu'un produit P est partitionné à l'ordre k quand P s'écrira sous forme d'un produit de k facteurs. On notera un produit P d'ordre k par : A un certain ordre, les partitions de P forment un ensemble noté : E( ) . E ( ) Ensemble des Partitions de P à l'ordre k Ensemble des produits avec = a1 x a2 x .... x ak (k facteurs) Il faut donc déterminer le nombre des partitions de . Nombre de partitions d'un produit : On notera NE( ) le nombre de partitions à l'ordre k du produit P (Cardinal de E( ) ,en tenant compte de la commutativité de la multiplication c'est à dire que la partition ( a x b ) est identique à la partition ( b x a ) et sans répétition de facteurs( a x a x b IMPOSSIBLE ). Exemple : P = 60 Ordre 1 ( k = 1 ) E( ) = { 60 } = = > NE ( ) = 1 Ordre 2 ( k = 2 ) E( ) = { (1x60) ; (2x30) ;(3x20); (4x15); (5x12); (6x10) } = = > NE( ) = 6 Ordre 3 ( k = 3 ) E( ) = { (1x2x30);(1x3x20);(1x4x15);(1x5x12);(1x6x10);(2x3x10);(2x5x6); (3x4x5) } = > NE( ) = 8 Ordre 4 ( k = 4 ) E( ) = {(1x2x3x10);(1x2x5x6);(1x3x4x5)} = = > NE( ) = 3 Ordre 5 ( k = 5 ) 60 ne peut se partitionner à l'ordre 5 car 1 x 2 x 3 x 4 x 5 = 5! = 120 > 60. Remarques importantes : 1) On constate que le nombre de partitions de P = 60 à tout ordre est inférieur au nombre de diviseurs ( 12 ) de 60. 2) On a décompté le diviseur trivial (1) alors que dans notre étude 1 est éliminé, ce qui diminuerait le nombre de partitions. oooooooooooooooooooo Résultats importants Soit Nn l'ensemble des n entiers consécutifs à partir de 1. Nn = { 1;2;3;...........;( n - 1);n } Soit n! = 1 x 2 x 3 x ...........x (n − 1) x n = Soit un produit quelconque de k facteurs distincts pris dans Nn avec 1 ≤ k ≤ n. On a les deux résultats évidents suivant : 1 ≤ ≤ n! et Ndiv( ) ≤ Ndiv( n! ) On peut évidemment étendre ces résultats au cas où Nn est un ensemble de n entiers non consécutifs. Dans ce cas, il faut et il suffit de remplacer n! par le produit des n facteurs (factorielle tronquée dans le sens facteurs non consécutifs) que l'on notera par analogie : Pn!. Nn = Ensemble de n entiers = { a1;a2; a3;.....;an }. Pn! = a1 x a2 x a3 x ........... x an ( entiers non nécessairement consécutifs ). On a donc les résultats similaires : ≤ Pn! et Ndiv( ) ≤ Ndiv( Pn! ) Conclusion : Soit Nn = Ensemble de n entiers Soit un produit de k facteurs pris dans Nn avec 1 ≤ k ≤ n On a la relation MAJORANTE : N( ) ≤ Ndiv(Pn !) pour tout k. On peut donc affecter à chaque partition ( ) un numéro d’ordre noté N°( ) tel que : N°( ) ≤ Ndiv(Pn!) Vérification avec l'exemple précédent : P = 60 Ndiv(60) = 12 et à tout ordre k ; 1 ≤ k ≤ 4 NE ( ) = 1 NE( ) = 6 NE( ) = 8 NE( ) = 3 Remarques sur cette relation : Cette relation est nettement suffisante pour la suite de l'étude de la compression. On pourra affiner cette relation qui va dépendre aussi de la programmation utilisée. Vu le codage antérieur du produit P, par exposant des nombres premiers dans sa décomposition, les simplifications sont importantes. Elle permettra aussi de faire des extrapolations relativement simples dans toute base, principalement des grandes bases ( 20;30;...et plus ). Une démonstration est donnée par la suite. ( Voir Annexe : Page 77 ; Ligne 3683 à Page 79 ; Ligne 3736 ). oooooooooooooooooooo On va appliquer cette relation pour le codage du numéro de P dans le cas de la PHASE3 en Base10. Rappel : PHASE3 Base10 L'étude va se porter ( en PHASE3 ) sur 887 cases après codage de 137 cases. oooooooooooooooooooo Base10 : Codage du Numéro de P Pour déterminer le nombre de bits nécessaire au codage du numéro de P on va considérer la majoration ( très large ) suivante : N°(P) ≤ Ndiv( P887! ) On aboutit au calcul suivant : Ndiv( P887! ) ≈ 1,857 x et à l'encadrement : ≈ 1,766 x ≤ ≈ 3,533 x soit Conclusion : Codage de N°(P) 241 Bits oooooooooooooooooooo On peut par conséquent en déduire la séquence de compression en PHASE3. oooooooooooooooooooo Base10 : Codage PHASE3 On va adopter cette forme de codage de Comp(.) pour la PHASE3. PHASE0 = = > Comp(.) = { NBe;Be;C1;C1023;1024; ….......} (768 bits) 216 ≤ NBe ≤ 510 = = > PHASE3 1) On continue les codages des 134 cases particulières à partir de la case C1024 (soit Bit13), de Bit14 à Bit147 (codage des 134 cases supérieures, semi-supérieures et d'imparité dans l'ordre croissant). 2) On code NBe;ph3 (9 bits) et Be;ph3 (1 bit) Bit 48 à Bit157 : codage de NBe;ph3 et Bit158 : codage de Be;ph3 3) On code le produit P sur 262 bits (68 NP) soit de Bit159 à Bit420. 4) On code le numéro du produit P sur 241 bits soit de Bit421 à Bit661. 5) On code par 107 Bits neutres Bn= 0 pour obtenir la compression voulue de 768 bits soit de Bit662 à Bit768. Remarque : Ces 107 bits neutres doivent être utilisés pour améliorer la compression et la décompression. Diverses méthodes sont possibles. On pourra entre autres, diminuer le numéro de P, en se rappelant aussi du fait que l'on pourra affiner ce numéro vu la majoration utilisée. Les codages fournis par ces 107 bits neutres ( cases ou nombre de cases ou .... ) détermineront la séquence de compression finale. ( Voir Annexe : Page 88 ; Ligne 4215 à Page 90 ; Ligne 4286 ). Décompression : Comme vu précédemment, la lecture de Comp(.) donne tous les renseignements nécessaires pour retrouver, à partir de 768 bits, la suite binaire originelle de 1024 bits. oooooooooooooooooooo Résumé Base 10 1024 bits 768 bits Gain en bits = 25 % (256 bits) Taux = 1024 / 768 ≈ 1,33 0 ≤ NBe ≤ 510 PHASE0 : Comp(.) = { NBe;Be;C1;C1023; C1024 ................... } (13 bits) 0 ≤ NBe ≤ 75 = = > PHASE1 = = > Comp(.) = { PHASE0 ; ......codage case sur 10 bits......... } 76 ≤ NBe ≤ 215 = = > PHASE2 = = > Comp(.) = { PHASE0; ..... codage par N° de combinaison ...... } 216 ≤ NBe ≤ 510 = = > PHASE3 = = > Comp(.) = { PHASE0;Codage de 134 cases( 134 bits);Codage de NBe;ph3 et Be;ph310 bits);Codage du produit P(262 bits);Codage de N°P(241 bits); 105 Bits neutres } Taux maximal = 1024 / 663 ≈ 1,54 ( sans bits neutres ) oooooooooooooooooooo On va montrer tout d'abord des études abrégées de bases inférieures à 10, pour bien visualiser la croissance du taux de compression avec la croissance de la base et déterminer la base de compression minimale. On va également étudier les Base20 ( ordre du méga ) et Base30 ( ordre du giga ) et prouver que les gains en bits atteignent les taux de 50% et 75 %. oooooooooooooooooooo Abrégé Base 9 Voir plus de détails ( Annexe : Page 65 ; Ligne 3067 à Page 67 ; Ligne 3172 ). = 512 = = > 512 cases : C1 = = > C512 Comp(Ba9) 393 bits Gain bits 119 (512-393 = 119) soit 23,24 % Taux(Ba9);maximal = 512 / 393 ≈ 1,30 PHASE0 0 ≤ NBe ≤ 254 ; NBe = = > 8 bits et Be = = > 1 bit Codage de NBe ;Be ;C1 ; C511 ; C512 = = > PHASE0 = = > 12 bits. PHASE1 0 ≤ NBe ≤ 43 = = > PHASE1 Codage d'une case en Ba9 9 bits ; il reste 6 bits libres PHASE2 44 ≤ NBe ≤ 111 = = > PHASE2 Combinaisons dans 509 cases. = = > N°(Combinaison) 381 bits. PHASE3 112 ≤ NBe ≤ 254 = = > PHASE3 Etude de P : 97 nombres premiers numérotés de = 2 à = 509. 43 cases supérieures,30 cases semi-supérieures et 1 case d'imparité ( NCCph3 = 74 cases codées ). Codage P = = > 233 bits Il reste 435 cases = = > Répartition : 435 = 217 + 218 d'où : 0 ≤ NBe;ph3 ≤ 217 avec ≤ 217 ≤ ; NBe;ph3 = = > 8 bits et Be;ph3 = = > 1bit P codé sur 39 NP de = 2 à = 167 Le nombre de diviseurs de P(435)! est : Ndiv(P(435)!) ≈ 3,398 x = = > N°(P) 138 bits oooooooooooooooooooo Abrégé Base 8 Voir plus de détails ( Annexe : Page 68 ; Ligne 3172 à Page 69 ; Ligne 3273 ). = 256 = = > 256 cases : C1 = = > C256 Comp(Ba8) 229 bits Gain bits 27 (256 − 229 = 27) soit 10,54 % Taux(Ba8);maximal = 256 / 229 = 1,12 PHASE0 0 ≤ NBe ≤ 126 ; NBe = = > 7 bits et Be = = > 1 bit Codage de NBe ;Be ;C1 ; C255 ; C256 = = > PHASE0 = = > 11 bits PHASE1 0 ≤ NBe ≤ 27 = = > PHASE1 Codage d'une case en Ba8 8 bits ; Il reste 2 bits libres. PHASE2 28 ≤ NBe ≤ 75 = = > PHASE2 Combinaisons dans 253 cases. = = > N°(Combinaison) 218 bits. PHASE3 76 ≤ NBe ≤ 126 = = > PHASE3 Etude de P : 54 nombres premiers numérotés de = 2 à = 251. 23 cases supérieures,16 cases semi-supérieures et 1 case d'imparité ( NCCph3 = 40 cases codées ). Codage P = = > 127 bits Il reste 213 cases = = > Répartition : 213 = 106 + 107 d'où : 0 ≤ NBe;ph3 ≤ 106 ; ≤ 106 ≤ ; NBe;ph3 = = > 7 bits et Be;ph3 = = > 1bit P codé sur 23 NP de = 2 à = 83 Le nombre de diviseurs de P(213)! est : Ndiv(P(213)!) ≈ 1,954 x = = > N°(P) 81 bits oooooooooooooooooooo On va maintenant voir les résultats sur les Bases 20 et 30, beaucoup plus importantes dans la pratique et confirmer les taux de compression prévus oooooooooooooooooooo Abrégé Base20 Voir plus de détails ( Annexe : Page 69 ; Ligne 3275 à Page 72 ; Ligne 3410 ). = 1 048 576 = = > C1 = = > C1048576 Ordre du mégabit ( ≈ 1 Million de bits ) Comp(Ba20) 524 288 bits Gain bits 524 288 soit 50% NBn PHASE3 304 961 Bits neutres Comp;min (Ba20) 284 962 bits ( > 75 % ) Taux(Ba20);maximal = 1048576 / 284 962 ≈ 3,679 On choisit de faire l'étude sur un gain de bits de 50%. PHASE0 0 ≤ NBe ≤ 524 286 ; NBe = = > 19 bits et Be = = > 1 bit Codage de NBe ;Be ;C1 ;C1048575 ;C1048576 = = > PHASE0 = = > 23 bits PHASE1 0 ≤ NBe ≤ 26 213 = = > PHASE1 Codage d'une case en Ba20 20 bits ; Il reste 5 bits libres. PHASE2 26214 ≤ NBe ≤ ( 26214 + X ) = = > PHASE2 Combinaisons dans 1048573 cases. 524 265 bits maximum. . Les calculs (détermination de X), tout à fait faisables, peuvent être abordés par coupures et formules, ou calculateur plus puissant. PHASE3 ( 26214 + X + 1 ) ≤ NBe ≤ 524 286 = = > PHASE3 Etude de P : 82 025 nombres premiers numérotés de = 2 à = 1 048 573. Codage P = = > 174 917 bits 38 635 cases supérieures : { = 524 309 ; …..... ; = 1 048 573 } Cases{ 524 309 ; ..….. ; 1 048 573 } 13 451 NP semi-supérieurs : { = 349529 ; …..... ; = 524287 } 26 902 cases semi-supérieures{ à et doubles (x2) } Codage case d'imparité C524288 avec 524 288 = Total : 65 538 Cases Codées ( 38 635+ 26902 + 1 = 65 538 ) Reste : 983 035 cases = = > Répartition : 983035 = 491 517 + 491 518 0 ≤ NBe;ph3 ≤ 491 517 = = > NBe;ph3 = = > 19 bits et Be;ph3 = = > 1 bit Après simplification, P codé sur 29 939 NP de = 2 à = 349 519 P 109 379 bits Codage du Numéro de P : N°(P) 110 002 bits ( Majoration ) Comp(ph3) = 284 962 bits ( 23 + 20 + 174 917+ 110 002 = 284 962 ) Avec taux = 50 % ; 239 326 bits neutres à utiliser ( 524 288 - 284 962 = 284 962 ) Des calculs plus précis nécessiteraient de connaître les décompositions en NP de toutes les cases restantes de la base20, ce qui est évidemment possible. L’utilisation des bits neutres, en nombre conséquent, est également à considérer. oooooooooooooooooooo Abrégé Base30 Voir plus de détails ( Annexe : Page 72 ; Ligne 3412 à Page 75 ; Ligne 3570 ). = 1 073 741 824 = = > C1 = = > C1073741824 Ordre du gigabit ( ≈ 1 Milliard de bits ) Comp(Ba30) 268 435 456 bits Gain bits 805 306 368 soit 75% NBn PHASE3 77 217 210 Bits neutres Comp;min (Ba30) 191 218 246 bits ( > 75 % ) Taux maximal(Ba30) = 1 073 741 824 / 191 218 246 ≈ 5,61 On choisit de faire l'étude sur un gain de bits de 75%. PHASE0 0 ≤ NBe ≤ 536 870 910 ; NBe = = > 29 bits et Be = = > 1bit Codage de NBe ; Be ; C1 ; C1073741823 ; C1073741824 = = > PHASE0 = = > 33 bits PHASE1 0 ≤ NBe ≤ 8 947 847 = = > PHASE1 Codage d'une case en Ba30 30 bits ; Il reste 27 bits libre. PHASE2 8 947 848 ≤ NBe ≤ ( 8 947 848 + X ) = = > PHASE2 Combinaisons dans 1 073 741 821 cases ; 268 435 423 bits maximum . Les calculs (détermination de X), tout à fait faisables, peuvent être abordés par coupures et formules, ou calculateur plus puissant. PHASE3 ( 8 947 848 + X + 1 ) ≤ NBe ≤ 536 870 910 = = > PHASE3 Etude de P 54 400 028 nombres premiers numérotés de = 2 à = 1 073 741 789. Codage P = = > 113 117 181 bits 26 207 278 NP supérieurs : { = 536870923 ; .…..... ; = 1 073 741 789 } 26 207 278 cases supérieures : Cases { 536870923 ; ….. ; 1073741789 } 8 987 318 NP semi-supérieurs : { = 357 913 931 ; ….. ; = 536 870 909 } 17 964 636 cases semi-supérieures : Cases { ( 357 913 931 et 357 913 931 x2) ;…............ ; ( 536 870 909 et 536 870 909 x2 ) } Codage case d'imparité inutile. Total : 44 171 914 Cases Codées ( 26207278 + 17964636 = 44171914 ) Reste : 1 029 569 907 cases = = > Répartition : 1 029 569 907 = 514 784 953 + 514 784 954 0 ≤ NBe;ph3 ≤ 514 784 953 = = > NBe;ph3 = = > 29 bits et Be;ph3 = = > 1 bit Après simplification, P codé sur 19 205 432 NP de = 2 à = 357 913 921 P 68 945 267 bits Codage du Numéro de P : N°(P) 78 101 002 bits ( Majoration ) Comp(ph3) = 191 218 213 bits Avec Taux = 75 % ; 77 217 210 bits neutres à utiliser (524 288 − 284 962 = 284 962) Des calculs plus précis nécessiteraient de connaître les décompositions en NP de toutes les cases restantes de la base30, ce qui est évidemment possible. L'utilisation des bits neutres, en nombre conséquent, est également à considérer. oooooooooooooooooooo On va conclure l'étude de la partie principale. On a montré que la Base Minimale de compression était la base 8. Base 8 : 256 bits 229 bits Par concaténations du nombre nécessaire de suites binaires de bits, et répétitions du processus dans une même base (b), tout fichier numérisé peut être compressé en une unique suite binaire de longueur inférieure à dépendant de b et du choix de compression effectué. Toutes les bases (b) avec b ≥ 8 étant des bases de compression, on peut utiliser toutes ( ou en partie) ces bases de compression. Au maximum de compression, on aura la compression PARFAITEMENT SANS PERTE suivante : Compression Fichier numérisé ( Poids quelconque) 229 bits Décompression Le taux théorique de compression est bien infini : = ==> + ∞ quand N ===> + ∞ oooooooooooooooooooo Taux de Compression Maximal Rappel : Le taux maximal de compression dans une base donnée est déterminé par la PHASE3, sans prendre en compte des bits neutres possibles. On a vu les résultats suivants : Taux;max( Ba8 ) = 256 / 229 ≈ 1,118 Taux;max( Ba9 ) = 512 / 393 ≈ 1,302 Taux;max( Ba10 ) = 1 024 / 663 ≈ 1,544 Taux;max( Ba20 ) = 1 048 576 / 284 962 ≈ 3,679 Taux;max( Ba30 ) = 1 073 741 824 / 191 218 246 ≈ 5,615 Conséquence : Le taux maximal de compression est croissant avec la base. En approximation, on peut dire que le passage d'une base ( b ) à une base ( b + 1 ) augmente le taux maximal de 0,9 environ. Taux;max( Ba( b+1) ) ≈ Taux;max( Ba(b) ) + 0,9. On peut donc en déduire une approximation valable pour toutes base (b) ; b ≥ 8. oooooooooooooooooooo Dans la partie ANNEXE, on va traiter les notions de restes, concaténations, partie fixe, des exemples de codage, des suggestions de programmation, des compléments, …... . On terminera par un abrégé général et les revendications. oooooooooooooooooooo ANNEXE Extrait Table Décomposition en NP ( Base 10 ) cases NP EXP NP EXP NP EXP NP EXP 2 2 1 3 3 1 4 2 2 5 5 1 6 2 1 3 1 …..... …..... …..... …..... …..... 100 2 2 5 2 101 101 1 102 2 1 3 1 17 1 …..... …..... …..... …..... …..... …..... …..... 349 349 1 350 2 1 5 2 7 1 …..... …..... …..... …..... …..... …..... …..... 450 2 1 3 2 5 2 451 11 1 41 1 452 2 2 113 1 …..... …..... …..... …..... …..... …..... …..... 615 3 1 5 1 41 1 616 2 3 7 1 11 1 …..... …..... …..... …..... …..... …..... …..... 749 7 1 107 1 750 2 1 3 1 5 3 …..... …..... …..... …..... …..... …..... …..... 898 2 1 449 1 899 29 1 31 1 900 2 2 3 2 5 2 …..... …..... …..... …..... …..... …..... …..... 1020 2 2 3 1 5 1 17 1 1021 1021 1 1022 2 1 7 1 73 1 1023 3 1 11 1 31 1 1024 2 10 Partie fixe La partie fixe de la compression doit contenir tous les renseignements nécessaires à la décompression du document compressé. Il faudra indiquer l'origine de la suite binaire compressée ( codage en octal, hexadécimal, ........ ) et nature du document originel ( texte, son, film, ...... ). Dans le codage de la partie fixe il faudra nécessairement indiquer le nombre de bits initial à coder / compresser ou des paramètres qui permettent de retrouver ce nombre: nombre de tranches de traitement en telle base, nombre de bits de restes éventuel. Ces renseignements serviront évidemment à la phase de décodage / décompression comme limite de décodage. Cette PARTIE FIXE de compression que l'on notera PF aura un poids informatique faible. PF doit avoir un poids constant, quel que soit le document à compresser. Remarque : Cette partie fixe pouvant être également compressé, elle peut-elle même être adaptée pour une compression simple ( par exemple : éviter le plus possible la PHASE3, être multiple parfait d'une certaine base, ...... ). oooooooooooooooooooo Notion de reste Soit Ω0 une suite binaire originelle. On suppose une compression en base (b) soit des compressions de suites binaires de bits. Le nombre de bits de Ω0 n'est pas nécessairement un multiple parfait de . Ω0 peut cependant s'écrire : Ω0 = K x + R0 avec 0 ≤ R0 On peut donc traiter ce reste R0 en fonction de différents paramètres, taille de R0, base choisie, .... . Si R0 est relativement petit il peut être directement « copier-coller » dans la partie fixe PF(rubrique Reste). Il est possible de compléter R0 par ( − R0 ) bits connus ( par exemple 0 ) et l'intégrer ainsi dans la compression. Cette opération doit être indiquée dans la partie fixe. En cours de compression, il peut apparaître différents restes R1,R2, ….. ,Rn. Cependant ces restes de compression ont une taille connue et constante donc plus faciles à traiter. Ils peuvent également être compressés à part en les concaténant : R1 + R2 + ….... + Rn = = > compression Exemple avec Reste : ( Voir Annexe : Pages 47 ; 48 ; Ligne 2165 à Ligne 2238 ). (A la suite) oooooooooooooooooooo Base 10 : Concaténation Soit Ω0 une suite binaire originelle. On va uniquement faire un exemple simple et en tirer les principales conclusions. Soit Ω0 = [A1;.A2;...;Ai;..;An] avec 1 ≤ i ≤ n, n suites binaires de 1024 bits consécutives. Rappel : Base10 : 1024 bits 768 bits ( gain de 25% en bits ). Exemple : n = 4 Ω0 = [A1;A2;A3;A4] Ω0 4096 bits ( 4 x 1024 = 4096 ). On effectue une première compression sur chaque Ai : Ai = = > Ai;c1 Ai (1024 bits) = = > Ai;c1 ( 768 bits ) Ai;c1 Compression de Ai après première compression. Par analogie, on notera : Ω0 = = > Ω0;c1 = [ A1;c1;A2;c1;A3;c1;A4;c1 ] On obtient donc : Ω0;c1 : 3072 bits On regroupe donc en 3 suites binaires de 1024 bits. Pour ne pas alourdir les notations on indicera uniquement sur i et j avec Ai;cj. Après regroupement et deuxième compression on obtient : Ω0;c2 = [ A1;c2; A2;c2; A3;c2 ] Ω0;c2 : 2304 bits La compression peut se continuer sur 2 suites de 1024 bits tout en gardant les 256 bits restants que l'on peut noter R2 = { 256 bits }. Après regroupement et troisième compression on obtient : Ω0;c3 = [ A1;c3; A2;c3 ] Ω0;c3 : 1536 bits La compression peut se continuer sur une suite de 1024 bits tout en gardant les 512 bits restants que l'on peut noter R3 = { 512 bits }. Après regroupement et quatrième compression on obtient : Ω0;c4 = [ A1;c4 ] et Ω0;c4 : 768 bits On obtient une compression telle que Ω0c4 + R2 + R3 = ( 768 ) + ( 256 ) + ( 512 ) La compression peut ainsi se prolonger en faisant le groupement : 768 + 256 + 512 = 2 x 768 = 1536 et 1536 = 1 x 1024 + 512 La compression peut encore se prolonger jusqu’à ce qu'on ait atteint la compression voulue. Différents algorithmes de concaténation peuvent être envisagés. Les restes peuvent être traités à part puis regrouper avec la compression principale, ou avoir un codage particulier, ..... . Il est surtout important de noter que l'on peut choisir la compression maximale atteinte, en fonction également du temps de compression que l'on s'accorde. Ceci confirme bien le Taux théorique de compression infini. Si Ω0 = = > infini et, après compression Ω0;c = fini alors : Taux : Ω0 / Ω0;c est INFINI. oooooooooooooooooooo Etude du cas Particulier : Gain de 50 % On rappelle que ce taux de 50% peut être atteint en particulier avec la base 20 ( ordre du méga ) et toute base supérieure. Avec ce gain de 50% on a la relation très simplifiée : Soit b une base de taux de compression de 50 % possible. compression bits = = = = > bits On considère le cas très particulier où la suite originelle Ω0 est de longueur x bits. Exemple : Base 20 ( b = 20 ) ; N = 3 = = > = 8 Ω0 est de longueur x = = 8 388 608 On a la relation : x = x x = x D'où les compressions verticales ( sans reste ) : 1-iére compression Ω0 { x bits } = = = = > Ω0;c1 { x bits } 2-iéme compression Ω0;c1 { x bits } = = = = > Ω0;c2 { x bits } 3-iéme compression Ω0;c2 { x bits } = = = = > Ω0;c3 { x bits } …......................................................................................................................... …......................................................................................................................... i-iéme compression Ω0;c(i-1) { x bits } = = = = > Ω0;ci { x bits } …......................................................................................................................... …......................................................................................................................... N-iéme compression Ω0;c(N-1) { x bits } = = = = > Ω0;cN { x bits } Ω0;c(N-1) { x bits } = = = = > Ω0;cN { x bits } Ω0;c(N-1) { x 2 bits } = = = = > Ω0;cN { bits } d'où : ( N+1)-iéme compression Ω0;cN) { bits } = = = = > Ω0;c(N+1) { bits } Fin de compression ou continuation avec des bases inférieures à b. On vérifie aussi : Ω0 / Ω0;c(N+1) = x / = 2 x = Si N = = = > infini alors Ω0 / Ω0;c = = = > infini Remarque de programmation : Par ajout de bits ( ou retrait de bits ), on peut toujours se ramener à ce type de concaténation, puis revenir à la vraie suite binaire originelle. Exemple : Soit Ω0 = { x 7 bits } = 8 = 7 + 1 Il suffit de rajouter une suite de bits connue (par exemple bits 0) et de compresser comme indiqué auparavant. En fin de décompression, il suffit d'enlever les bits nuls. Cet ajout de bits doit être évidemment mentionné dans la partie fixe de compression. Ce taux de compression de 50% peut être fixé ( sauf pour les petites bases) ce qui facilite les concaténations et donnent un grand nombre de bits neutres dans les grandes bases, ce qui simplifie en particulier la PHASE3. oooooooooooooooooooo PROGRAMME et SOUS-PROGRAMMES On se place dans une base b. Soit Ω0 la suite binaire originelle à compresser. Soit PROG;comp le programme de compression. On désignera par SPROG les sous-programmes. Il semble naturel d'associer un sous-programme pour chaque phase. PHASE0 = = > SPROG;ph0 PHASE1 = = > SPROG;ph1 PHASE2 = = > SPROG;ph2 PHASE3 = = > SPROG;ph3 SPROG;ph0 doit agir en premier pour découper en suite binaire de bits et coder les nombres du bit d'étude NBe qui détermine la phase suivante, ainsi que Be et les 3 cases C1; C1023; C1024. SPROG;ph0 peut aussi coder en partie fixe (PF) le nombre de bits total à compresser ainsi que les ajouts, restes, .... possibles. Premier passage de compression : SPROG;ph1,2,3 agissent dans leurs cas respectifs en fonction de NBe. Ω0 = = > Ω0;c1 avec ( Ω0;c1 Deuxième passage de compression : PROG;comp envoie la deuxième compression surΩ0;c1 d'où les mêmes opérations sur Ω0;c1. SPROG;ph0 suivi de SPROG;ph1,2,3. Ω0;c1 = = > Ω0;c2 avec ( Ω0;c2 …........................................................................................... …........................................................................................... et ainsi de suite jusqu'à la N-iéme compression souhaitée. …........................................................................................... …........................................................................................... N-iéme passage de compression : Ω0;c(N-1) = = > Ω0;cN avec ( Ω0;cN Au final, PROG;comp enregistre la compression. En décompression, il suffit de considérer le programme de décompression PROG;décomp qui effectue les opérations strictement inverses du programme de compression PROG;comp. Conclusion : Il y a différentes versions possibles de PROG;comp et PROG;décomp pouvant dépendre des conditions d'utilisation et des choix effectués. Remarque importante : Les temps de compression et décompression doivent être sensiblement égaux. oooooooooooooooooooo On va voir des exemples en PHASE1;2;3. oooooooooooooooooooo Cas triviaux La suite originelle de 1024 bits sera notée A. Cas trivial n°1 Soit la suite A de 1024 bits (0). A = { C1 = 0; C2 = 0; ..... ;C500 = 0; .... ;C1023 = 0; C1024 = 0 } Base 10 Suite binaire A Cases C1 C2 … C10 …. …. …. C500 …. …. …... C1022 C1023 C1024 Bits 0 0 0 0 0 0 0 0 0 0 0 0 0 0 COMPRESSION PHASE0 Rappel : Sb = Somme des bits de C2 à C1022. Sb = 0 + 0 + ..... + 0 + 0 = 0 Sb = 0 = = > Sb ≤ 510 = = > Be = 1 et NBe = Sb = 0 Codage de NBe sur 9 bits NBe = 0 Bit1 à Bit9 000000000 Codage de Be sur 1 bit Be = 1 Bit10 1 Codage de C1;C1023;C1024 sur 1 bit chacune C1 = 0 Bit11 0 C1023 = 0 Bit12 0 C1024 = 0 Bit13 0 Rappel : PHASE0 { NBe ;Be ;C1 ;C1023 ;C1024 } PHASE0 { 000000000;1;0;0;0;....... } Rappel : 0 ≤ NBe ≤ 75 = = > PHASE1 NBe = 0 = = > 0 ≤ 0 ≤ 75 = = > PHASE1 NBe = 0 = = > Aucune case à coder = = > 755 bits neutres Bn (=0). Conclusion : Rappel : Comp( ) est sur 768 bits. Comp(A) { PHASE0;PHASE1;Bn } { 000000000;1;0;0;0; ...755bits (0) ... } DECOMPRESSION Elle est donnée par la lecture de Comp(A) sur 768 bits. Lecture Bit1 à Bit9 000000000 NBe = 0 Lecture Bit10 1 Be = 1 Lecture Bit11 0 = > C1 = 0 Lecture Bit12 0 C1023 = 0 Lecture Bit13 0 C1024 = 0 Rappel : Be' = complémentaire de Be soit ( Be'(1) = 0 et Be'(0) = 1 ) 1) Compléter les cases C1;C1023;C1024 par leurs bits = = > ( 0;0;0 ) 2) Compléter les NBe cases de Be par Be = = > aucune case avec bit 1 3) Compléter les (1021 − NBe) cases restantes par Be' = = > bit 0 dans les 1021 cases. Conclusion : On retrouve la suite binaire A. A = { C1= 0 ;C2 = 0 ;.....;C500 = 0;.... C1023= 0; C1024 = 0 } oooooooooooooooooooo Cas trivial n°2 Soit la suite A de 1024 bits (1). A = { C1=1 ;C2 =1 ; ..... ;C500 = 1;.... ; C1023=1; C1024= 1 } Base 10 Suite binaire A Cases C1 C2 … C10 … …. …. C500 …. …. …... C1022 C1023 C1024 Bits 1 1 1 1 1 1 1 1 1 1 1 1 1 1 COMPRESSION PHASE0 Rappel : Sb = Somme des bits de C2 à C1022. Sb = 1 + 1 + …... + 1 + 1 = 1021 Sb = 1021 = = > Sb > 510 = = > Be = 0 et NBe = 1021 − Sb = 1021 – 1021 = 0 Codage de NBe sur 9 bits NBe = 0 Bit1 à Bit9 000000000 Codage de Be sur 1 bit Be = 0 Bit10 0 Codage de C1;C1023;C1024 sur 1 bit chacune C1 = 1 Bit11 1 C1023 = 1 Bit12 1 C1024 = 1 Bit13 1 Rappel : PHASE0 { NBe;Be;C1;C1023;C1024 } PHASE0 { 000000000;0;1;1;1; ....... } Rappel : 0 ≤ NBe ≤ 75 = = > PHASE1 NBe = 0 = = > 0 ≤ 0 ≤ 75 = = > PHASE1 NBe = 0 = = > Aucune case à coder = = > 755 bits neutres Bn (=0). Conclusion : Rappel : Comp( ) est sur 768 bits. Comp(A) { PHASE0;PHASE1;Bn } { 000000000;1;1;1;1;..755bits (0) ... } DECOMPRESSION Elle est donnée par la lecture de Comp(A) sur 768 bits. Lecture Bit1 à Bit9 000000000 NBe = 0 Lecture Bit10 0 Be = 0 Lecture Bit11 1 C1 = 1 Lecture Bit12 1 C1023 = 1 Lecture Bit13 1 C1024 = 1 Rappel : Be' = complémentaire de Be soit ( Be'(1) = 0 et Be'(0) = 1 ) 1) Compléter les cases C1;C1023;C1024 par leurs bits = = > ( 1;1;1 ) 2) Compléter les NBe cases de Be par Be = = > aucune case avec bit 0 3) Compléter les ( 1021 – NBe ) cases restantes par Be' = = > bit 1. Conclusion : On retrouve la suite binaire A. A = { C1= 1 ;C2 = 1 ;.....;C500 = 1; .... ; C1023= 1; C1024 = 1 } Remarque sur ces 2 cas : Les différences de codage entre ces 2 cas sont sur la valeur de Be et les 3 cases C1; C1023; C1024. oooooooooooooooooooo EXEMPLE PHASE1 La suite originelle de 1024 bits sera notée A. Soit la suite A : { C1= 0 ;C2 = C10 = C20 = C30 = C40 = 1 ; Autres cases bit 0 } Base 10 Suite binaire A Cases C1 C2 … C10 … C20 …. C30 …. C40 …... C1022 C1023 C1024 Bits 0 1 0 1 0 1 0 1 0 1 0 0 0 0 COMPRESSION PHASE0 Rappel : Sb = Somme des bits de C2 à C1022. Sb = 1 + 0 ... + 0 + 1 + 0 ... + 0 + 1 + 0 ... + 0 + 1 + 0 ... + 0 + 1 + 0 ... + 0 + .... + 0 + 0 = 5 Sb = 5 = = > Sb ≤ 510 = = > Be = 1 et NBe = Sb = 5 Codage de NBe sur 9 bits NBe = 5 Bit1 à Bit9 000000101 Codage de Be sur 1 bit Be = 1 Bit10 1 Codage de C1;C1023;C1024 sur 1 bit chacune C1 = 0 Bit11 0 C1023 = 0 Bit12 0 C1024 = 0 Bit13 0 Rappel : PHASE0 { NBe;Be;C1;C1023;C1024 } Rappel : PHASE0 { 000000101;1;0;0;0; ....... } 0 ≤ NBe ≤ 75 = = > PHASE1 NBe = 5 = = > 0 ≤ 5 ≤ 75 = = > PHASE1 NBe = 5 = = > 5 cases à coder chacune sur 10 bits. C2 Bit14 à Bit23 0000000010 C10 Bit24 à Bit33 0000001010 C20 Bit34 à Bit43 0000010100 C30 Bit44 à Bit53 0000011110 C40 Bit54 à Bit63 0000101000 Le codage des 5 cases de Be nécessitant 50 bits, la séquence de compression de A doit être complétée par 705 bits neutres Bn (755−50 = 705) Conclusion : Rappel : Comp( ) est sur 768 bits Comp (A) { PHASE0 ; PHASE1; Bn } { 000000101;1;0;0;0;0000000010; 0000001010;0000010100;0000011110;0000101000; …. …….. 705bits (0) ….. } DECOMPRESSION Elle est donnée par la lecture de Comp(A) sur 768 bits. Lecture Bit1 à Bit9 000000101 NBe = 5 Lecture Bit10 1 Be = 1 Lecture Bit11 0 C1 = 0 Lecture Bit12 0 C1023 = 0 Lecture Bit13 0 C1024 = 0 Rappel : Be' = complémentaire de Be soit ( Be'(1) = 0 et Be'(0) = 1 ) 1) Compléter les cases C1;C1023;C1024 par leurs bits = = > ( 0;0;0 ) 2) Compléter les NBe cases de Be par Be = = > 5 cases avec bit 1 = = > Bit 1 dans;C2; C10; C20; C30;C40 (Lecture de Bit14 à Bit63 par tranche de 10 bits). 3) Compléter les (1021 – NBe ) cases restantes par Be' = = > bit 0 dans les 1016 cases restantes ( 1021 − 5 = 1016 ). Conclusion : On retrouve la suite binaire A. A = { C1= 0 ; C2 = C10 = C20 = C30 = C40 = 1 ; Autres cases bit 0 } oooooooooooooooooooo EXEMPLE PHASE2 On va expliciter un exemple simple, vu les grandes valeurs de calculs, en PHASE2. La suite originelle de 1024 bits sera notée A. Soit la suite A . A = { C1 = 0 ; C2 ..à..C76 = 1 ;C77 ..à.. C85 = 0 ; C86 = 1; Autres cases bit 0 } Base 10 Suite binaire A Cases C1 C2 C3 … C76 C77 …. C85 C86 C87 …... C1022 C1023 C1024 Bits 0 1 1 1 1 0 0 0 1 0 0 0 0 0 COMPRESSION PHASE0 : Rappel : Sb = Somme des bits de C2 à C1022. Sb = 1 + 1 + .... + 1 + 0 + .... + 0 + 1 + 0 + 0 + .... + 0 + 0 = 76 Sb = 76 = = > Sb ≤ 510 = = > Be = 1 et NBe = Sb = 76 Codage de NBe sur 9 bits NBe = 76 Bit1 à Bit9 001001100 Codage de Be sur 1 bit Be = 1 Bit10 1 Codage de C1;C1023;C1024 sur 1 bit chacune C1 = 0 Bit11 0 C1023 = 0 Bit12 0 C1024 = 0 Bit13 0 Rappel : PHASE0 { NBe;Be;C1;C1023;C1024 } PHASE0 { 001001100;1;0;0;0; .......} Rappel : 76 ≤ NBe ≤ 215 = = > PHASE2 NBe = 76 = = > 76 ≤ 76 ≤ 215 = = > PHASE2 Rappel : En PHASE2, il suffit de coder le numéro de combinaison cherché sur 754 bits, connaissant la combinaison N°1 grâce à NBe. NBe = 76 = = > N°1 = { C2;C3;C4;C5;........................;C75;C76;C77 } La combinaison de la suite binaire A considérée est : A = { C2;C3;C4;C5;........................;C75;C76 ;C86 } Il est nécessaire et suffisant de 9 incrémentations de pas (+1) pour le passage : C77 = = > C86. donc le numéro de A est : 9 + 1 = 10 N°(A) = N°10 = 10 Codage de N°(A) sur 754 bits N°(A) = 10 Bit14 à Bit767 000.....0001010 Codage de 1 bit neutre Bn = 0 NBn = 1 Bit768 0 Codage de A pour PHASE2 = = > { 000.......0001010;0 } (755 bits) On obtient finalement la séquence de compression suivante pour la suite A : Comp(A) = ( NBe ; Be ; C1 ; C1023 ; C1024 ; N°(A) ; Bn ) Comp(A) = ( 001001100 ;1;0;0;0; 000.......0001010;0 ) (768 bits) DECOMPRESSION Elle est donnée par la lecture de Comp(A) sur 768 bits. Lecture Bit1 à Bit9 001001100 NBe = 76 Lecture Bit10 1 Be = 1 Lecture Bit11 0 C1 = 0 Lecture Bit12 0 C1023 = 0 Lecture Bit13 0 C1024 = 0 Lecture Bit14 à Bit767 000.......0001010 N°(A) = 10 Lecture Bit768 inutile ( bit neutre ) NBe = 76 = = > N°1 = { C2;C3;C4;C5;........................;C75;C76;C77 } N°(A) = 10 = = > C77 = = > C86 = = > Be dans 76 cases { C2;C3;C4;C5;........................;C75;C76;C86 } Rappel : Be' = complémentaire de Be soit ( Be'(1) = 0 et Be'(0) = 1 ) 1) Compléter les cases C1;C1023;C1024 par leurs bits = = > ( 0;0;0 ) 2) Compléter les NBe cases de Be par Be = = > 76 cases avec bit 1 3) Compléter les 945 ( 1021 – 76 ) cases restantes par Be' = bit 0. Conclusion : On retrouve la suite binaire A. A = { C1= 0 ; C2 ..à..C76 = 1 ; C77 ..à.. C85 = 0 ; C86= 1 ; Autres cases bit 0 } oooooooooooooooooooo Remarque : Par mesure de simplification on a codé N°(A) sur le cas maximal soit 754 bits. Or dans le cas de NBe = 76 il suffirait de 369 bits donc des simplifications possibles que l'on verra dans les améliorations de codage en PHASE2. oooooooooooooooooooo EXEMPLE PHASE3 On va aborder une approche de programmation en phase3. On va se placer dans le cas de 887 cases d'étude comprise entre C2 et C1022. Rappel : 134 cases supérieures, semi-supérieures et imparité ont été codées en PHASE3. On rappelle que toutes les décompositions des cases en facteurs premiers sont connues ( classées sous forme de table ). Ces décompositions nécessitent 68 NP de = 2 à = 337. Des valeurs particulières pour chaque NP sont également connues et peuvent également être classées par table : Exposant maximal du NP dans le produit Exposant maximal du NP dans les décompositions Maximum de formes possibles dans les décompositions Classement ordre croissant des multiples des NP Exemples : Le = 2 est au maximum à l'exposant 8 dans une case. Le = 337 ne peut être que sous les formes 337, (337x2), (337x3) (1 facteur ou 2 maximum). On va donner des explications avec des petites valeurs de NBe, même si celles-ci ne correspondent pas à des valeurs réelles de PHASE3. Soit un produit de cases P. P est connu, codé par sa décomposition en NP. P = × × ….... × = Exemple : Soit NBe = 4 Be dans 4 cases Soit Be en C2, C3, C8, C10. P = 2 x 3 x 8 x 10 = 480 = x x x ( x ) = x x = x x . P nécessite uniquement 3 NP ( 2; 3; 5 ). Toutes les partitions de P vont donc se faire sur ces 3 NP et leurs multiples. On forme le premier produit possible que l'on notera P0, suivant le principe de calcul d'une factorielle, ordre croissant et termes consécutifs le plus possible. Ce produit P0 servira de produit de référence. Rappel : C1 est codée donc pas d'élément neutre 1 dans P. Remarque : NBe! = 4! s'exprime sur 3 cases ( et non 4 ). On adoptera la notation classique de la factorielle : «Factorielle de N N! On indicera par « t » si la factorielle est tronquée, dans le sens que les facteurs ne sont pas nécessairement consécutifs, mais classés dans l'ordre croissant des NP autorisés et de leurs multiples. Exemple : 5!= 2 x 3 x 4 x 5 = 120 Si on omet le NP = 3 on aura la factorielle tronquée : = 2 x 4 x 5 x 7 = 280 ( l'omission de 3 entraine l'omission de 6 = 2 x 3 ). Si on omet le NP = 2 on aura la factorielle tronquée : = 3 x 5 x 7 x 9 = 945 ( l'omission de 2 entraine aucun facteur pair soit ni 4,6,8). Par mesure de simplification, on précisera seulement si la factorielle est tronquée ou non, sauf nécessité de précision. Remarque : N! et ont ( N – 1 ) facteurs soit ( N – 1 ) cases. Le facteur 1 est neutre. Exemple : sans = 3 et = 7 = 2 x 4 x 5 x 8 x 10 x 11 x 13 7 premiers facteurs sans multiples de 3 et 7. Remarque : Si on veut commencer le produit par une autre valeur que 2, on le précisera sans notation particulière. Exemples : 5! à partir de 3 = = > 3 x 4 x 5 x 6 ( 4 facteurs ) sans NP = 3 à partir de 5 = = > 5 x 7 x 8 x 10 ( 4 facteurs sans multiples de 3 ) Reprise Exemple ( P = 480 ) : P = 2 x 3 x 8 x 10 = 480 = x x 4 cases ; 3 NP consécutifs 4! = 2 x 3 x 4 = 24 = x x = x = x ( 8 x 3 = 24 ) On posera comme premier produit possible : P0 = 4! x ( P / 4!) P0 = 24 x ( 480 / 24 ) = 24 x 20 = 2 x 3 x 4 x 20 Ou P0 = x x [( x x ) / ( x )] = x x ( x x ) = x x ( x ) donc P0 Suite0 = { C2; C3; C4; C20 } Remarque : On en déduit que la case minimale est C2 et la maximale C20. A partir de P0, il faut déterminer toutes les autres partitions possibles de P. Pour cela on va voir la notion de distribution de la dernière case sur les précédentes. C20 = = > 20 = ( x ) 20 = ( x ) x ( 1 ) Cas1 20 = ( ) x ( ) Cas2 20 = x ( x ) Cas3 20 = ( x ) x ( ) Cas4 Ra p pel : Il ne peut y avoir de répétitions de cases. Cas1 : ( x ) x (1) **Distribution impossible car ( 1 ) interdit. Fin de Distribution de Cas1 Cas2 : ( ) x ( ) On choisit de distribuer dans l'ordre croissant des NP. **Distribution de avec fixe ( C5 fixe ) P1 = ( x ) x x x = x x x = = > { 8; 3; 4; 5 } = = > Suite1 = { C3; C4; C5; C8 } P2 = x ( x ) x x = = > { 2; 12; 4; 5 } = = > Suite2 = { C2; C4; C5; C12 } P3 = x x ( x ) x = = > { 2; 3; 16; 5 } = = > Suite3 = { C2; C3; C5; C16 } Fin de Distribution de Cas2 Cas3 : ( ) x ( x ) **Distribution de avec ( x ) fixe ( C10 fixe ) P4 = x ( x ) x ( x ( x ) = = > { 2; 6; 4; 10 } = = > Suite4 = { C2; C4; C6; C10 } P5 = x x ( x ) x ( x ) = = > { 2; 3; 8; 10 } = = > Suite5 = { C2; C3; C8; C10 } Fin de Distribution de Cas3 Cas4 : ( x ) x ( ) **Distribution de ( x ) avec fixe ( C5 fixe ) P6 = x ( x ) x ( x ) x = = = > { 2; 6; 8; 5 } = = > Suite6 = { C2; C5; C6; C8 } Fin de Distribution de Cas4 Fin de Distribution Conclusion : P peut avoir 7 partitions de P0 à P6. Dans notre cas, il faut considérer P5 soit la Suite5 = { C2; C3; C8; C10 } Remarques : On peut facilement vérifier que la première case ne peut prendre que les 2 valeurs C2 et C3. En effet : 4! à partir de 4 = 4 x 5 x 6 x 7 = 840. ( 840 > 480 ) Ndiv(P) = (5+1) x (1+1) x (1+1) = 6 x 2 x 2 = 24 et 7 oooooooooooooooooooo On peut envisager une deuxième méthode, par recherche de case en case puis classement, vu que les calculs de produits par table de décomposition sont relativement simples. On va expliciter la méthode en décimal. NBe = 4 donc on cherche 4 cases que l'on notera X1; X2; X3; X4. On notera N(a)! la factorielle de N à partir de a soit le produit des N facteurs dans l'ordre croissant à partir de a, sachant que ces facteurs sont pris dans les multiples des NP considérés. Remarque : La définition est légèrement différente de la précédente (N facteurs et non (N − 1). 1) On détermine toutes les valeurs possibles de X1. Valeurs de X1 4(2)! = 2 x 3 x 4 x 5 = 120 et 120 ≤ 480 4(3)! = 3 x 4 x 5 x 6 = 360 et 360 ≤ 480 4(4)! = 4 x 5 x 6 x 8 = 960 et 960 > 480 Conclusion pour X1 : X1 peut prendre les valeurs 2 ou 3. On notera : X1= ( 2;3 ) 2) On détermine toutes les valeurs possibles de X2 en fonction de X1. X1 = 2 Fixé = = > P / 2 = 480 / 2 = 240 Reste3 cases X2;X3;X4. 3(3)! = 3 x 4 x 5 = 60 et 60 ≤ 240 3(4)! = 4 x 5 x 6 = 120 et 120 ≤ 240 3(5)! = 5 x 6 x 8 = 240 et 240 ≤ 240 Conclusion pour X1 = 2 : X2 = ( 3;4;5 ) X1 = 3 Fixé = = > P / 3 = 480 / 3 = 160 Reste3 cases X2;X3;X4. 3(4)! = 4 x 5 x 6 = 120 et 120 ≤ 160 3(5)! = 5 x 6 x 8 = 240 et 240 > 160 Conclusion pour X1 = 3 : X2 = ( 4 ) 3) On détermine toutes les valeurs possibles de X2 en fonction de X1et X2. ( X1;X2 ) fixé : ( X1;X2 ) = ( 2;3 ) = = > P / 3 = 480 / 2 x 3 = 80 Reste 2 cases X3;X4 2(4)! = 4 x 5 = 20 et 20 ≤ 80 2(5)! = 5 x 6 = 30 et 30 ≤ 80 2(6)! = 6 x 8 = 48 et 48 ≤ 80 2(8)! = 8 x 9 = 72 et 72 ≤ 80 2(9)! = 9 x 10 = 90 et 90 > 80 Conclusion : ( X1;X2 ) = ( 2;3 ) = = > X3 = ( 4;5;6;8;9 ) ( X1;X2 ) = ( 2;4 ) = = > P / 2x4 = 480 / 8 = 60 Reste 2 cases X3;X4 2(5)! = 5 x 6 = 30 et 30 ≤ 60 2(6)! = 6 x 8 = 48 et 48 ≤ 60 2(8)! = 8 x 9 = 72 et 72 > 60 Conclusion : ( X1;X2 ) = ( 2;4 ) = = > X3 = ( 5;6 ) ( X1;X2 ) = ( 2;5 ) = = > P / 2x5 = 480 / 10 = 48 Reste 2 cases X3;X4 2(6)! = 6 x 8 = 48 et 48 ≤ 48 Conclusion : ( X1;X2 ) = ( 2;5 ) = = > X3 = ( 6 ) ( X1;X2 ) = ( 3;4 ) = = > P / 3x4 = 480 / 12 = 40 Reste 2 cases X3;X4 2(5)! = 5 x 6 = 30 et 30 ≤ 40 2(6)! = 6 x 8 = 48 et 48 > 40 Conclusion : ( X1;X2 ) = ( 3;4 ) = = > X3 = ( 5 ) Il ne reste plus qu'à déterminer X4 pour conclure. ( X1;X2 ) = ( 2;3 ) = = > X3 = ( 4;5;6;8;9 ) D'où les différents cas : (X1;X2;X3) = (2;3;4) = = > P / 2x3x4 = 480/24 = 20 = = > Suite{ C2;C3;C4;C20 } (X1;X2;X3) = (2;3;5) = = > P / 2x3x5 = 480/30 = 16 = = > Suite{ C2;C3;C5;C16 } (X1;X2;X3) = (2;3;6) = = > P / 2x3x6 = 480/36 = 13,3 NON ENTIER (X1;X2;X3) = (2;3;8) = = > P / 2x3x8 = 480/48 = 10 = = > Suite{ C2;C3;C8;C10 } (X1;X2;X3) = (2;3;9) = = > P / 2x3x9 = 480/54 = 8,8 NON ENTIER ( X1;X2 ) = ( 2;4 ) = = > X3 = ( 5;6 ) D'où les différents cas : ( X1;X2;X3 ) = ( 2;4;5 ) = = > P / 2x4x5 = 480/40 = 12 = = > Suite{ C2;C4;C5;C12 } ( X1;X2;X3 ) = ( 2;4;6 ) = = > P / 2x4x6 = 480/48 = 10 = = > Suite{ C2;C4;C6;C10 } ( X1;X2 ) = ( 2;5 ) = = > X3 = ( 6 ) D'où le cas : ( X1;X2;X3 ) = ( 2;5;6 ) = = > P / 2x5x6 = 480/60 = 8 = = > Suite{ C2;C5;C6;C8 } ( X1;X2 ) = ( 3;4 ) = = > X3 = ( 5 ) D'où le cas : ( X1;X2;X3 ) = ( 3;4;5 ) = = > P/3x4x5 = 480/60 = 8 = = > Suite{ C3;C4;C5;C8 } Conclusion : On retrouve bien les 7 cas de partitions. Il suffit de les numéroter par exemple de P0 à P6. Remarque : il ne s'impose pas de prendre la même numérotation que précédemment. Au vu de la méthode adoptée, il semble naturel de les classer par ordre croissant en fonction de la première case puis de la suivante etc. On aurait donc : Suite0 = { C2;C3;C4;C20 } Suite1 = { C2;C3;C5;C16 } Suite2 = { C2;C3;C8;C10 } Suite3 = { C2;C4;C5;C12 } Suite4 = { C2;C4;C6;C10 } Suite5 = { C2;C5;C6;C8 } Suite6 = { C3;C4;C5;C8 } Remarques : Pour les calculs des factorielles, des formules de passage, plus rapides, peuvent être utilisées. Des calculs de factorielles peuvent être évités, vu les conditions sur les exposants des Nombres Premiers. En fonction du nombre de bits neutres disponibles, il peut être intéressant de coder quelques cases particulières .Par exemple les cases extrêmes ( première et dernière cases) des cases intermédiaires( case médiane, .....). Diverses possibilités sont envisageables. oooooooooooooooooooo Base9 = 512 = = > 512 cases : C1 = = > C512 PHASE0 Codage de C1; C511; C512 = = > 3 bits Il reste 509 cases ( 512 – 3 = 509) = = > Répartition : 509 = 254 + 255 0 ≤ NBe ≤ 254 ; 128 ≤ 254 ≤ 256 ; ≤ 254 ≤ NBe = = > 8 bits et Be = = > 1bit PHASE0 = = > 12 bits ( 12 = 8 + 1 + 3 ) La PHASE3 donne le nombre de bits minimum de codage. PHASE3 Etude de P 97 nombres premiers numérotés de = 2 à = 509. Codage P = = > 233 bits 43 cases supérieures : {257;263;269;271;277;281;283;293;307;311;313;317;331;337;347;349;353;359;367;373;379;383;389;397;401;409;419;421;431;433;439;443;449;457;461;463;467;479;487;491;499;503;509} 30 cases semi-supérieures : {173;179;181;191;193;197;199;211;223;227;229;233;239;241;251;346;358;362;382;386:394;398;422;446;454;458;466;478;482;502} Après codage des 73 ( 43 + 30 = 73 ) cases supérieures et semi-supérieures il reste 436 cases ( 509 – 73 = 436 ). Codage case d'imparité C256 avec 256 = Il reste 435 cases ( 436 − 1 = 435 ) = = > Répartition : 435 = 217 + 218 d'où 0 ≤ NBe;ph3 ≤ 217 ; 128 ≤ 217 ≤ 256 ; ≤ 217 ≤ NBe;ph3 = = > 8 bits et Be;ph3 = = > 1 bit Simplification de P (après suppression des NP supérieurs, semi-supérieurs) P codé sur 39 NP de = 2 à = 167 P 160 bits ( 233 – 73 = 160 ) Codage du Numéro de P On a N435 cases. Le nombre de diviseurs de P(435)! est : Ndiv(P(435)!) ≈ 3,398 x ≈ 1,742 x ; ≈ 3,484 x = = > N°(P) 138 bits PHASE3 = = > 381 bits ( 381 = 233 + 1 + 138 + 9 ) 112 ≤ NBe ≤ 254 = = > PHASE3 ( Voir après PHASE2 pour le minimum 112 ) Comp(.) PHASE0 + PHASE3 ( 12 ) + ( 381 ) = 393 bits Comp(Ba9) 393 bits Gain bits 119 (512-393=119) soit 23,24 % Taux(Ba9) = 512 / 393 = 1,302 Rappel taux(Ba10) ≈ 1,333 Remarque : Dans cette solution on ne décompte pas de bits neutres ( ce qui serait toutefois possible ). On déduit la PHASE1 et la PHASE2 à partir de Comp(Ba9) = 393 bits PHASE1 Codage d'une case en Ba9 9 bits 393 = 387 + 6 = 9 x 43 + 6 = = > 0 ≤ NBe ≤ 43 = = > PHASE1 Remarque : il reste 6 bits libres PHASE2 Combinaisons dans 509 cases , 381 bits maximum On a les résultats suivants : C(111;509) ≈ 3,684 x 2,462 x ≤ 4,925 x ; d'où : 44 ≤ NBe ≤ 111 = = > PHASE2 Remarque : Il ne reste aucun bit libre. On déduit :112 ≤ NBe ≤ 254 = = > PHASE3. oooooooooooooooooooo Base8 = 256 = = > 256 cases : C1 = = > C256 PHASE0 Codage de C1; C255; C256 = = > 3 bits Il reste 253 cases ( 256 – 3 = 253) = = > Répartition : 253 = 126 + 127 0 ≤ NBe ≤ 126 ; 64 ≤ 126 ≤ 128 : ≤ 126 ≤ NBe = = > 7 bits et Be = = > 1 bit PHASE0 = = > 11 bits ( 11 = 7 + 1 + 3) La PHASE3 donne le nombre de bits minimum de codage. PHASE3 Etude de P 54 nombres premiers numérotés de = 2 à = 251. Codage P = = > 127 bits 23 cases supérieures : {131;137;139;149;151;157;163;167;173;179;181;91;193;197;199;211;223;227;229;233;239; 241;251} 16 cases semi-supérieures : {89;97;101;103;107;109;113;127;178;194;202;206;214;218;226;254} Après codage des 39 ( 23 + 16 = 39 ) cases supérieures et semi-supérieures il reste 214 cases ( 253 − 39 = 214 ). Codage case d'imparité C128 avec 128 = Il reste 213 cases ( 214 – 1 = 213 ) = = > Répartition : 213 = 106 + 107 d'où 0 ≤ NBe;ph3 ≤ 106 ; 64 ≤ 106 ≤ 128 ; ≤ 106 ≤ NBe;ph3 = = > 7 bits et Be;ph3 = = > 1 bit Simplification de P ( après suppression des NP supérieurs, semi-supérieurs ) P codé sur 23 NP de = 2 à = 83 P 88 bits ( 127 − 39 = 88 ) Codage du Numéro de P On a N213 cases. Le nombre de diviseurs de P(213)! est : Ndiv(P(213)!) ≈ 1,954 x ≈ 1,208 x ; ≈ 2,417 x N°(P) 81 bits PHASE3 = = > 218 bits ( 218 = 127 + 1 + 81 + 9 ) 76 ≤ NBe ≤ 126 = = > PHASE3 ( Voir après PHASE2 ) Comp(.) PHASE0 + PHASE3 ( 11 ) + ( 218 ) = 229 bits Comp(Ba8) 229 bits Gain bits 27 (256-229=27) soit 10,54 % taux(Ba8) = 256 / 229 ≈ 1,118 Remarque : Dans cette solution on ne décompte pas de bits neutres ( ce qui serait toutefois possible ). On déduit la PHASE1 et la PHASE2 à partir de Comp(Ba8) = 229bits PHASE1 Codage 1 case en Ba8 8 bits 218 = 216 + 2 = 8 x 27 + 2 = = > 0 ≤ NBe ≤ 27 = = > PHASE1 PHASE2 Combinaisons dans 253 cases. On a les résultats suivants : C(75;253) = 3,344 x ; 2,106 x ≤ 4,212 x = = > 28 ≤ NBe ≤ 75 = = > PHASE2 Remarque : Il ne reste aucun bit libre. On déduit ; 76 ≤ NBe ≤ 126 = = > PHASE3 oooooooooooooooooooo Base 20 = 1 048 576 = = > Ordre du mégabit ( ≈ 1 Million de bits ). 1 048 576 cases : C1 = = > C1048576 PHASE0 Codage de C1; C1048575; C1048576 = = > 3 bits Il reste : 1 048 573 ( 1 048 576 – 3 = 1 048 573 ) cases = = > Répartition : 1 048 573 = 524 286 + 524 287 0 ≤ NBe ≤ 524 286 ; 262 144 ≤ 524 286 ≤ 524 288 ; ≤ 524 286 ≤ NBe = = > 19 bits et Be = = > 1 bit PHASE0 = = > 23 bits ( 23 = 19 + 1 + 3 ) PHASE1 Codage 1 case en Ba20 20 bits Après PHASE0 : Il reste 524 265 bits ( 524 288 – 23 = 524 265 ) On a : 524 265 = 26 213 x 20 + 5 D'où : 0 ≤ NBe ≤ 26 213 = = > PHASE1 ( 5 Bits neutres ) PHASE2 Combinaisons dans 1 048 573 cases. 524 265 bits maximum. 26 214 ≤ NBe ≤ ( 26 214 + X ) = = > PHASE2 Il faudrait déterminer X tel que : C( 26 214 + X;1 048 573 ) ≤ Les calculs sont très faisables avec l'aide d'un ordinateur plus adapté. Des coupures de calcul peuvent être envisagées. La PHASE3 donne le nombre de bits minimum de codage. PHASE3 Etude de P 82 025 nombres premiers numérotés de = 2 à = 1 048 573. Codage P = = > 174 917 bits 38 635 NP supérieurs : { = 524 309 ; .…..... ; = 1 048 573 } 38 635 cases supérieures : Cases { 524 309 ; …... ; 1 048 573 } 13 451 NP semi-supérieurs :{ = 349529 …..... = 524 287 } ( 43390 – 29940 + 1 = 13451 ) 26 902 cases semi-supérieures : ( 13451 x 2 = 26902 ) Cases { (349529 et 349529 x 2) ; …................ ; (524 287 et 524 287 x 2 ) } Après codage des 65 637 ( 38635 + 26902 = 65637 ) cases supérieures et semi-supérieures il reste 982 936 cases ( 1 048 573 – 65637 = 982936 ). Codage case d'imparité C524288 avec 524 288 = Il reste 983 036 cases ( 983036 – 1 = 983035 ). = = > Répartition : 983 035 = 491 517 + 491 518 0 ≤ NBe;ph3 ≤ 491 517 ; 262 144 ≤ 491 517 ≤ 524 288 ; ≤ 491 517 ≤ NBe;ph3 = = > 19bits et Be;ph3 = = > 1 bit Après simplification de P P codé sur 29 939 NP de = 2 à = 349 519 174 917 − 65 635 = 109 282 P 109 282 bits Codage du Numéro de P : On a N983035 cases. Les calculs sont évidemment effectués après suppression des NP supérieurs et semi-supérieurs et case d'imparité ainsi que 3 cases de PHASE0. Par mesure de simplification de calcul, chaque NP est supposé être à l'exposant maximal donné par le nombre de bits de codage nécessaire. Exemple : Soient les 5 NP : = 17 = = > = 31. Chaque NP doit être codé sur 16 bits avec = 65 536. Pour le calcul du nombre de diviseurs on prendra donc l'exposant de ces 5 NP égaux à 65 536. Cette majoration est très importants vu qu'en réalité l'exposant est décroissant de à avec = 32 768 comme minorant. Des calculs exacts nécessiteraient de connaître les décompositions en NP des 983 037 cases . Cette majoration est nettement probante. Des calculs précis sont évidemment possibles et seront faits lors de la programmation finale. Une majoration est suffisante pour nos calculs. Le nombre de diviseurs de P(983037 )! est : Ndiv( P(983037 )! ) ≈ 3,15 x On supposera : Ndiv( Ba20;ph3 ) = 4 x En termes de bits on considérera la relation suivante : ≈ 1,071 x . On considérera que : ≈ Dans ces conditions et sachant que 32925 / 301 ≈ 109,38 = = > 110. 4 x = x = x = = Conclusion : N°( P ) 110 002 bits On constate que le codage du numéro de P(110 002 bits) est inférieur au codage de P(174 919 bits) par ses nombres premiers NP. On constate que le codage du numéro de P(110 002 bits) est sensiblement égal au codage de P( 109 282 bits ) après simplification de cases. PHASE3 = = > 219 304 bits ( 219 304 = 109 282 + 110 002 + 1 + 19 ) D'où Comp,minimale(Ba20) = Comp( PHASE0 + PHASE3 ) = 219 304 Comp,min(Ba20) = 219 327 bits Si gain en bits de 50 % : NBn = 304 961 Bits neutres ( 524 288 – 219 327 = 304 961 ) En conclusion le gain en bits en Base20 pourrait être plus important que 50 % ( et même 75 % ) au détriment du nombre de bits neutres en PHASE3. Ceux-ci permettront des calculs plus simples et plus rapides en PHASE3. En cas de préférence d'une compression plus forte, les résultats en PHASE1 et PHASE2 seront modifiés en conséquence . oooooooooooooooooooo Base 30 = 1 073 741 824 = = > Ordre du giga-bit ( ≈ 1 Milliard de bits ). 1 073 741 824 cases : C1 = = > C1073741824 Compression souhaitée Comp(Ba30) 268 435 456 bits Gain bits 805 306 368 soit 75% PHASE0 Codage de C1; C1073741823; C1073741824 = = > 3 bits Il reste : 1 073 741 821 cases ( 1 073 741 821 – 3 = 1 073 741 821 ). = = > Répartition : 1 073 741 821 = 536 870 910 + 536 870 911 0 ≤ NBe ≤ 536 870 910 ; 268 435 456 ≤ 536 870 910 ≤ NBe = = > 29 bits et Be = = > 1 bit PHASE0 = = > 33 bits ( 33 = 29 + 1 + 3 ) PHASE1 Codage 1 case en Ba30 30 bits Après PHASE0 ; Il reste 268 435 423 bits ( 268 435 456 – 33 = 268 435 423 ) On a : 268 435 423 = 8 947 847 x 30 + 27 D'où : 0 ≤ NBe ≤ 8 947 847 = = > PHASE1 ( 27 Bits neutres ) PHASE2 Combinaisons dans 1 073 741 821 cases. 268 435 423 bits maximum. 8 947 848 ≤ NBe ≤ ( 8 947 848 + X ) = = > PHASE2. Il faudrait déterminer X tel que : C( 8 947 848 + X; 1 073 741 821 ) ≤ Les calculs sont très faisables avec l'aide d'un ordinateur plus adapté. Des coupures de calcul peuvent être envisagées. La PHASE3 donne le nombre de bits minimum de codage. PHASE3 Etude de P 54 400 028 nombres premiers numérotés de : = 2 à = 1 073 741 789. Codage P = = > 113 117 181 bits 26 207 278 NP supérieurs : { = 536870923 ; .…..... ; = 1 073 741 789 } 26 207 278 cases supérieures : Cases { C536870923 ; ….. ; C1073741789 } 8 987 318 NP semi-supérieurs : { = 357 913 931 ; …..... ; = 536 870 909 } ( 28 192 750 – 19 205 433 + 1 = 8 987 318 ) 17 964 636 cases semi-supérieures : ( 8 987 318 x 2 = 17 964 636 ) Cases { ( 357 913 931 et 357 913 931 x 2) ; …............. ; ( 536 870 909 et 536 870 909 x 2 ) } Après codage des 44 171 914 ( 26 207 278+ 17 964 636 = 44 171 914 ) cases supérieures et semi-supérieures il reste 1 029 569 907 cases ( 1 073 741 821 – 44 171 914 = 1029569907 ). Codage case d'imparité non nécessaire = = > Répartition : 1 029 569 907 = 514 784 953 + 514 784 954 0 ≤ NBe;ph3 ≤ 514 784 953 ; 268 435 456 NBe;ph3 = = > 29bits et Be;ph3 = = > 1 bit Après simplification de P P codé sur 19 205 432 NP de = 2 à = 357 913 921 ( 113 117 181 − 44 171 914 = 68 945 267 ) P 68 945 267 bits Codage du Numéro de P : On a N1029569907 cases. Les calculs sont évidemment effectués après suppression des NP supérieurs et semi-supérieurs ainsi que 3 cases de PHASE0. Par mesure de simplification de calcul, chaque NP est supposé être à l'exposant maximal donné par le nombre de bits de codage nécessaire (idem Base20). Exemple : Soient les 5 NP : = 17 = = > = 31. Chaque NP doit être codé sur 26 bits avec = 67 108 864. Pour le calcul du nombre de diviseurs on prendra donc l'exposant de ces 5 NP égaux à 67 108 864. Cette majoration est très importante vu qu'en réalité l'exposant est décroissant de à avec = 33 554 432 comme minorant. Des calculs exact nécessiteraient de connaître les décompositions en NP des 1029569907 cases. Cette majoration est nettement probante. Des calculs précis sont évidemment possibles et seront faits lors de la programmation finale. Une majoration est suffisante pour nos calculs. Le nombre de diviseurs de P(1029569907)! est : Ndiv( P(1029569907 )! ) ≈ 2,31 x On supposera : Ndiv( Ba30;ph3 ) = 4 x . En termes de bits on considérera la relation suivante : ≈ 1,071 x On considérera que : = Dans ces conditions et sachant que 23508384 / 301 ≈ 78100,94 = = > 78 101. 4 x = x = x = = Conclusion : N°( P ) 78 101 002 bits On constate que le codage du numéro de P ( 78 101 002 bits) est inférieur au codage de P( 113 117 181 bits) par ses nombres premiers NP. On constate que le codage du numéro de P ( 78 101 002 bits) est sensiblement voisin au codage de P ( 68 945 267 bits ) après simplification de cases. PHASE3 = = > 191 218 213 bits. (191 218 213 = 113 117 181 + 78 101 002 + 1 + 29 ) D'où Comp,minimale(Ba30) = Comp( PHASE0 + PHASE3 ) = 191 218 213 + 33 D'où Comp,minimale(Ba30) = Comp( PHASE0 + PHASE3 ) = 191 218 213 + 33 = 191 218 246 bits. Comp,min(Ba30) = 191 218 246 bits Si gain en bits de 75 % : NBn = 77 217 210 Bits neutres. ( 268 435 456 – 191 218 246 = 77 217 210 ) En conclusion le gain en bits en Base30 pourrait être plus important que 75 % au détriment du nombre de bits neutres en PHASE3. Ceux-ci permettront des calculs plus simples et plus rapides en PHASE3. En cas de préférence d'une compression plus forte, les résultats en PHASE1 et PHASE2 seront modifiés en conséquence. On peut également se contenter d'un gain en bits de 50 % , ce qui augmenterait fortement le nombre de bits neutres donc améliore vitesse et simplicité de la PHASE3. oooooooooooooooooooo Exemples de Codage de NP dans P Étude de NP1 = 2 dans le produit P = 2 se retrouve dans la décomposition de toutes les cases paires ( 512 cases ). Son exposant maximal dans la décomposition est 10 car = 1024. Remarque : On retrouvera ce résultat dans toutes les bases ( b ).L'exposant maximal de = 2 est égal à b en base b. On applique la formule : emax = E( A / NP ) + E( A / ) + E( A / ) + …. + E(A / ) avec A = 1024 ; NP = 2 ; p = 10. emax= E( / ) + E( / ) + E( / ) + E( / ) + E( / ) + E( / ) + E( / ) + E( / ) + E( / ) + E( / ) = + + + + + + + + + = + + + + + + + + + = 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 1023. L’égalité emax = 1 023 signifie donc que = 2 peut se présenter dans le produit P avec un exposant de valeurs comprises entre 0 et 1023 soit 1024 cas (1024 = 1 023 + 1). On en déduit le codage de = 2 sur 10 bits car = 1024. Codage de = 2 = = > 10 bits. Remarque : On peut généraliser à toute base b ce résultat obtenu en base 10. Le nombre premier = 2 se codera dans le produit sur b bits. Tout autre nombre premier se codera sur p bits avec p Étude de NP2 = 3 dans le produit P = 3 se retrouve dans la décomposition de toutes les cases multiples de 3 ( 341 cases ). Son exposant maximal dans la décomposition est 6 car = 729 (729 ≤ 1 024) et = 2187 (2187 > 1024). emax = E( / ) + E( / ) + E( / ) + E( / ) + E( / ) + E( / ) = E( 1024 / 3 ) + E( 1024 / 9 ) + E( 1024 / 27 ) + E( 1024 / 81 ) + E( 1024 / 243 ) + E( 1024 / 729 ) = E( 341,3 ) + E( 113,7 ) + E( 37,9 ) + E( 12,6 ) + E( 4,2 ) + E( 1,4 ) = 341 + 113 + 37 + 12 + 4 + 1 = 508. L’égalité emax = 508 signifie donc que = 3 peut se présenter dans le produit P avec un exposant de valeurs comprises entre 0 et 508 soit 509 cas (509 = 508 +1). En conclusion, en base 10, = 3 présente 509 (= 508 + 1) cas possibles dans le produit des cases premières. On en déduit le codage de = 3 sur 9 bits car . Codage de = 3 = = > 9 bits. oooooooooooooooooooo Démonstration : N ( ) ≤ Ndiv( P ) _ On rappelle ce résultat classique : Soit la série : Se = + + + + ….. = + + + + … . = Se est la somme des inverses des puissances de 2. Essentiel : Se est une série géométrique de raison . Se est une série CONVERGENTE car sa raison est inférieure à 1 ( La suite tend vers 0 pour n tendant vers l'infini. Rappel : La somme des n premiers termes d'une suite géométrique de premier terme a et de raison q est : Sn = a x . Se converge donc vers 2 : En effet, 1 x ( 1 - 0 ) / ( 1 - 1/2 ) = 1 x ( 1 / ) = 1 x 2 = 2 Soit P un produit décomposé en facteur premiers : P = × × ….. × = Alors Ndiv( P ) = (e1 +1) x (e2 +1) x ........ x (ek +1) = = N ( Par simplification, on notera Ndiv( P ) = N ) Rappel : est dit partitionné à l'ordre k si P est produit de k facteurs. E( ) est l'ensemble des partitions de P à l'ordre k. N( ) est le nombre de partitions de P à l'ordre k, soit cardinal [ E ( ) ]. La multiplication étant commutative, l'ordre des facteurs n'est pas pris en compte c'est à dire que : a1 x a2 x ........ x ak = a2 x a1 x ........ x ak = ak x a2 x ....... x a1 1 seule partition. On va faire les calculs en considérant aussi les diviseurs triviaux 1 et P. Ceci est donc une majoration vu que dans notre cas le facteur 1 est éliminé. De plus on ne tiendra pas compte du fait que dans notre cas l'ensemble est borné par la base, ce qui élargit encore la majoration. Ordre 1 k = 1 E( ) = { P } et N( ) = 1 Ordre 2 k = 2 N( ) = N / 2 En effet, chaque diviseur est multiplié par un autre diviseur ( N cas ). Pour des raisons de commutativité, on doit diviser par 2 ( N / 2 cas ). On se ramènera à cette égalité pour les calculs aux ordres supérieurs. Ordre 3 k = 3 Premier facteur fixé = 1 = = > N / 2 cas de Deuxième facteur fixé = NP le plus petit avec exposant ≠ 0 ( minimum = 1 ). On pose ce NP égal à A. On pose P1 = P / A : P = A x P / A P / A = = > N( P / A ) diviseurs Donc P / A est sur 2 facteurs et N( P / A ) ≤ N Il faut enlever évidemment les diviseurs du premier facteur 1. Donc avec A fixé on aura la majoration suivante : Majoration des partitions : { [ N – N / 2 - N(P1) / 2 ] } / 2 ≤ [ N – N / 2 ] / 2et [ N – N / 2 ] / 2 = (N/2) / 2 = N / 4 On peut réitérer le calcul en fixant le troisième facteur possible et tant que possible. On obtiendra la majoration : N( ) ≤ + + + + ….... ≤ x ( + + + ........... ) ≤ x ( + +...........) ≤ x Se ≤ x 2 ≤ N. N( ) ≤ + + + + ….... ≤ x ( + + + ........... ) ≤ x ( + +...........) ≤ x Se ≤ x 2 ≤ N. Ce calcul peut se répéter à tout ordre k possible. Conclusion : N( ) ≤ Ndiv(P) Remarques : Cette majoration est importante en termes de nombre de partitions mais beaucoup moins en termes de nombres de bits nécessaire au codage du numéro de P. De plus, suivant l'utilisation des bits neutres ( dépendant aussi du taux de compression choisi ), un certain nombre de cases supplémentaires peuvent être codées ( nombre qui peut être relativement important ) donc diminution des nombres de diviseurs et des cas de partitions. La programmation définitive fixée affinera la recherche du numéro de P. oooooooooooooooooooo On va expliciter quelques améliorations de codage possibles, pouvant apporter dans certains cas des simplifications et un gain de vitesse d'exécution. oooooooooooooooooooo Complément de codage en PHASE1 En PHASE1 : 0 ≤ NBe ≤ 75. Dans tous les cas il reste 5 bits neutres Bn inutilisés. = 32. En fait, tous les cas de NBe amenant à la PHASE1, peuvent se regrouper sous le codage de NBe = 0. Ceci permet de libérer et récupérer 75 valeurs de NBe (1 = = > 75) qui doivent servir à simplifier en partie des cas de PHASES 2 et 3, phases plus complexes. Il suffit pour cela d'introduire la case impossible, par exemple la case C0 codée sur 10 bits par (0000000000). Après le codage classique de la PHASE1 des cases de Be, il suffit d'indiquer de stopper la lecture en décompression dès que 10 bits nuls(0) sont consécutifs (C0 impossible). Dans le cas particulier maximal, NBe = 75 tranches de 10 bits (non consécutivement nulles) pour 75 cases et seront suivis de 5 bits neutres Bn = 0. On peut aussi se servir des 5 bits inutilisés pour faire un premier tri. = 32 et 32 x 3 = 92 > 76 1 sous-cas sur 5 bits peut englober 3 cas de NBe. Exemple : Sous-cas ( 00000 ) = = > NBe = 0 ou 1 ou 2 = = > Lecture des cases sur 30 bits maximum …......................................................................... Sous-cas ( 00001 ) = = > NBe = 3 ou 4 ou 5 = = > Lecture des cases sur 60 bits maximum …......................................................................... Conclusion : PHASE1 = = > Possibilité de coder tous les cas de PHASE1 en NBe = 0. 75 valeurs ( 1 = = > 75 ) de NBe libres pour codage de cas de PHASES 2 ou 3. oooooooooooooooooooo Complément de Programmation en PHASE2 Ce qui suit est une approche de programmation possible pour le numéro de combinaison ( en compression et décompression ). Rappel : Base 10 ; 76 ≤ NBe ≤ 215 = = > PHASE2 On va se placer dans le cas de NBe = 76. Rappel : L'étude se fait sur 1021 cases : C2 = = > C1022 NBe = 76 donc on peut choisir comme première combinaison possible la suite : { C2;C3; ….... ;C75;C76;C77 } Par contre on va noter cette suite ( Suite;0) donc commencer la numérotation à 0 et non pas 1. (Suite;0) = { C2;C3; …....;C75;C76;C77 } On peut introduire une notion d'ordre. Ordre0 A l'ordre0 on a la ( Suite;0 ) : ( Suite;0 ) = { C2;C3; …....;C75;C76;C77 } Ordre1 A l'ordre1, on va dire qu'une seule case peut varier par rapport à la ( Suite;0 ) donc nécessairement la case C77. C77 peut donc prendre les valeurs : C78 = = > C1022 1022 – 77 = 945 soit 945 valeurs possibles. On pose Emax = 945 Ordre1 : 945 = C(1;945 suites possibles. (Suite;1) = { C2;C3; …....;C75;C76;C78 } (Suite;2) = { C2;C3; …....;C75;C76;C79 } …................................................................... (Suite;945)= { C2;C3; …....;C75;C76;C1022 } Ordre2 A l'ordre 2, on va dire que seulement 2 cases peuvent varier par rapport à la (Suite;0) donc nécessairement les cases C76 et C77. La première suite d'ordre 2 sera donc : (Suite;945+1) = (Suite;946) = { C2;C3; …....;C75;C77;C78 } Au total on peut avoir : 945 + 944 + 943 + ....... + 2 + 1 = 446 985 = C( 2;945 ) = C( 2;Emax ) suites possibles. (Suite;946) = { C2;C3; …....;C75;C77;C78 } (Suite;947) = { C2;C3; …....;C75;C77;C79 } ….................................................................... (Suite;447930) = { C2;C3; ….... ;C75;C1021;C1022 } Ordre3 A l'ordre3, on va dire que seulement 3 cases peuvent varier par rapport à la (Suite;0) donc nécessairement les cases C75; C76 et C77. La première suite d'ordre 3 sera donc : (Suite;447930 + 1) = (Suite;447931) = { C2;C3; …....;C76;C77;C78 } Au total on peut avoir : 140 205 240 = C(3;945) = C(3;Emax) suites possibles. (Suite;447931) = { C2;C3; …....;C76;C77;C78 } (Suite;447932) = { C2;C3; …....;C76;C77;C79 } ….................…..................................................... ….................…..................................................... (Suite;140653170) = { C2;C3; …....;C1022;C1021;C1022 } De proche en proche, on peut numéroter toutes les combinaisons à tout ordre. L'ordre maximal est évidemment la valeur de NBe. Dans notre cas l'ordre maximal serait 76. Dans un ordre donné, on peut introduire les écarts « e » entre les différentes cases par rapport à la (Suite;0). En cas de possibilité de bits neutres, il peut être intéressant de coder des ordres, des sous-ordres ( ordre dans un ordre donné ). Il peut être aussi intéressant de coder la première case qui a varié par rapport à (Suite;0) ainsi que la dernière case, ce qui détermine plus précisément l'écart maximal Emax. Plusieurs variantes sont possibles. oooooooooooooooooooo Améliorations de codage en PHASE2 Retour sur EXEMPLE PHASE2 NBe = 76 = = > C(76;1021) ≈ 1,469 x ≈ 7,880 x ≤ 1,576 x ≈ ; et 755 – 386 = 369 PHASE2 : NBe = 76 386 Bits ( 369 bits neutres Bn = 0 ) Dans l'exemple traité avec NBe = 76 on a codé le numéro de combinaison sur 754 bits. Or 386 bits suffisent donc il reste 369 bits inutilisés ( 755 – 386 = 369 ). Il resterait donc 652 cases ( 1021 − 369 = 652 ) donc la combinaison doit se calculer uniquement sur 652. On a les résultats suivants : C( 76;652 ) ≈ 4,277 x ≈ 3,499 x et ≈ 6,999 x d'où donc C(76;652) 335 bits. On peut donc continuer les calculs vu que l'on a décompté 386 bits et que seulement 335 suffisent. Or 386 – 335 = 51 donc on peut coder 51 cases supplémentaires. Il restera 652 – 59 = 593 cases. Or C(76;593) ≈1,971 x ≈ 1,708 x et ≈ 3,417 x d'où donc C(76;593) 324 bits. Or 335 – 324 = 11 donc on peut coder 11 cases supplémentaires . Il restera 593 – 11 = 582 cases. Dernier calcul : C(76;582) ≈ 4,301 x ≈ 4,271 x et ≈ 8,543 x d'où donc C(76;582 322 bits Remarque : Ces types de calculs et de simplifications peuvent se faire sur un certain nombre de NBe de PHASE2. Plus NBe va croitre, moins les simplifications seront importantes. Quand elles sont possibles, ces simplifications doivent améliorer les vitesses de compression / décompression. oooooooooooooooooooo CONDITIONNELLE : Suites de début et de fin Rappel : PHASE0 13 bits = ( NBe;Be;C1;C1023;C1024 ) Comp( ) = { PHASE0; ….... 755 bits ....... } On peut envisager une simplification de codage dans certains cas particulier, applicable dans tous les cas de NBe possibles donc intégrable dans les 3 PHASES 1;2;3. On considère les 755 bits restants et la répartition : 755 = 752 + 3. Cette conditionnelle va jouer sur 752 bits, les 3 bits restants servant à préciser si on est dans cette conditionnelle ou pas, et dans quel type. Explications : Après la PHASE0, il reste 1021 cases de C2 à C1022. On a : 1021 − 752 = 269 On appellera « Suite de début » que l'on notera « Suite;d » la suite des 269 cases consécutives de C2 à C270. On appellera « Suite de fin » que l'on notera « Suite;f » la suite des 269 cases consécutives de C754 à C1022. On va envisager 2 types de conditionnelle. Si Suite;d est une suite d'un unique bit alors on aura la conditionnelle de type 1. Si Suite;f est une suite d'un unique bit alors on aura la conditionnelle de type 2. Il faut nécessairement préciser la valeur de l’unique bit. d'où les 2 cas dans chaque type : Suite;d(0) Suite de début avec bit 0 ( bit 0 dans ( C2 à C270 ) Suite;d(1) Suite de début avec bit 1 ( bit 1 dans ( C2 à C270 ) Suite;f(0) Suite de fin avec bit 0 ( bit 0 dans ( C754 à C1022 ) Suite;f(1) Suite de fin avec bit 1 ( bit 1 dans ( C754 à C1022 ) Conséquence : Si on se trouve dans un cas de telle conditionnelle, il suffit de « copier – coller » dans Comp( ) la suite de 752 bits restante : 1) suite APRES la Suite;d ( type 1) « copier – coller » { C271; C272; …...;C1022 } 2) suite AVANT la Suite;f ( type 2) « copier – coller » { C2; C3; …...;C270 } Remarques : Cette conditionnelle peut être intégrer pour tout cas de NBe. La décompression est évidente. Cette conditionnelle peut être très intéressante, en particulier dans les PHASES 2 et 3. On va voir un exemple : Exemple : Soit la suite A : { C1;C2 = C3 = ….... = C269 = C270 = 1 ; Autres cases bit quelconque ; C1023; C1024 } Base 10 Suite binaire A Cases C1 C2 C3 ….. C269 C270 C271 ….. ….. ….. ….. C1022 C1023 C1024 Bits X 1 1 1 1 1 Bits quelconques X X La PHASE0 est effectuée de façon classique. Programmation Conditionnelle : Faire la Somme des bits des cases C2 à C270 = = > S(cond;type1) Si S(cond;type1) =270 alors Coder « Conditionnelle type1 avec bit 1 » ( Suite;d(1) ) Si S(cond;type1) = 0 alors Coder « Conditionnelle type1 avec bit 0 » ( Suite;d(0) ) Sinon : Faire la Somme des bits des cases C754 à C1022 = = > S(cond;type2) Si S(cond;type2) =270 alors Coder « Conditionnelle type2 avec bit 1 » ( Suite;f(1) ) Si S(cond;type2) = 0 alors Coder « Conditionnelle type2 avec bit 0 » ( Suite;f(0) ) Sinon : Coder « pas de conditionnelle » = = > Codage classique Phase1;2;3. Dans l'exemple on aurait donc : COMPRESSION S(cond;type1) = 270 = = > Suite;d(1) = = > codage sur 3 bits ( 001 par exemple ) = = > « copier – coller » { C271; C272; …...;C1022 }. = = > Comp(A) = { PHASE0;001; C271; C272; …... ; C1022 } DECOMPRESSION Lecture des 3 bits de Conditionnelle ( 001 ) = = > Conditionnelle de type1 avec bit1 ( Suite;d(1) ) = = > bit 1 dans cases C2 à C270 « copier – coller » 752 bits depuis Comp(A) Compléter par la lecture des cases C1;C1023;C1024 de la PHASE0 On retrouve la suite binaire originelle A. Remarques: En décompression la lecture des bits pour savoir si on se trouve dans ce cas de Conditionnelle ou non peuvent être lus en premier, car cette conditionnelle ne dépend ni de NBe ni de Be, ceux -ci devant être évidemment codés et lus en cas de non conditionnelle ( 000 ). Vu la nécessité d'introduire des bits de codage de conditionnelle, en cas d'intégration de celle-ci, il faudra revoir les valeurs de NBe en PHASE1,2,3 qui différeront de très peu. oooooooooooooooooooo Amélioration de codage en PHASE3 Codage PHASE3 en PHASE2 Rappel : PHASE3 = = > 216 ≤ NBe ≤ 510 134 cases supplémentaires sont déjà codées donc il reste 887 cases d'étude. Après codage PHASE0, 134 cases, NBe;ph3 et Be;ph3, il reste 611 bits ( 768 − 13 - 134 – 10 = 611 ). On peut voir intuitivement que pour des NBe voisins de216, le codage serait « presque faisable » comme en PHASE2. On a le résultat suivant : ≈ 8,498 x Exemple : Soit un cas de PHASE3 pour NBe = 216. On suppose que les 134 cases supplémentaires codées soient toutes occupées par Be. Alors nécessairement Be = Be;ph3 et NBe;ph3 = NBe – 134 = 216 − 134 = 82 On a le résultat suivant : C(82;887) ≈ 2,368 x donc C(82;887) ≤ Conséquence : Ce cas peut se coder en PHASE2 ( plus simple ). Il est évidemment impératif d'introduire une conditionnelle sur NBe;ph3 dépendant des 134 cases codées que l'on va déterminer. On a les résultats suivants : ≈ 8,498 x et C(165;887) ≈ 3,946 x donc C(165;887) ≤ C(166;887) ≈ 1,716 x donc C(166;887) > Conséquence : Le maximum de combinaison autorisé est :C(165;887). Pour NBe = 216, il faut donc au minimum que Be soit dans 51 cases des 134 cases codées ( 216 − 165 = 51 ). On peut poser comme conditionnelle : Si NBe ≥ 216 et NBe;ph3 ≤ 165 alors Codage Type PHASE2 avec N°(combinaison) 661 bits Cette conditionnelle peut s'appliquer uniquement pour 216 ≤ NBe ≤ 350 (216+134 =350). Remarque : Si cette conditionnelle est adoptée, elle ne nécessite pas de bits supplémentaires pour la mentionner. Savoir que NBe;ph3 ≤ 165 est suffisant. oooooooooooooooooooo Conditionnelles sur Produit P Conditionnelle sur P impair Soit un cas de NBe de PHASE3 : 216 ≤ NBe ≤ 510 Le codage de 137 cases est effectué et il reste 887 cases. Le calcul de P par exposants est fait ainsi que la détermination de NBe;ph3 et Be;ph3. Soit P impair c'est à dire que l'exposant de 2 est nul : aucune case paire. Conséquence : Be peut se trouver uniquement dans les 406 cases impaires. Or le maximum de combinaisons est atteint pour : C(203;406) ≈ 6,54 x . 5,16 x ≤ 1,03 x ≈ 5.16 x et ≈ 1.03 x Donc : = = > C(203;406) 402 bits Conclusion : En PHASE3, dans le cas particulier où P est impair, la compression peut être traitée en PHASE2, ce qui apporte une simplification. Cette conditionnelle doit être évidemment mentionnée dans la séquence de compression Comp( ). Remarque : Cette conditionnelle peut être élargie à des cas de produits P « presque impair ». On peut désigner par ce terme de « produit presque impair » des produits pairs avec très peu de facteurs pairs. La parfaite connaissance des facteurs pairs permet de se ramener à un cas de produit impair. Application en base 10 : La PHASE0,134cases supplémentaires,NBe;ph3,Be;ph3 nécessitent 157 bits de codage (13 + 134 + 10 = 157). Il faut réserver 402 bits pour le codage ( Type PHASE2 ) si P impair. Il reste donc 209 bits libres ( 768 – (157+402) ) avec 209 = 20 x 10 + 9. On peut donc se ramener au cas P impair tant que les facteurs (cases) pairs sont inférieurs ou égal à 20. ces cases paires doivent être codées chacune sur 10 bits. oooooooooooooooooooo Conditionnelle sur P pair On peut faire une analogie de codage avec certains cas de produit P pair. On peut appeler, par exemple, un produit « pair pur » un produit fait uniquement de facteurs pairs. Dans notre cas, il y a 481 cases paires ( 481 facteurs pairs ). Or le maximum de combinaisons est atteint pour : C ( 240;481 ) ≈ 2,26 x 1.95 x ≤ 3.90 x et ≈ 1.95 x et ≈ 3.90 x Donc : = = > C(240;481) 477 bits Conclusion : En PHASE3, dans le cas particulier où P est pair pur, la compression peut être traitée en PHASE2, ce qui apporte une simplification. Cette conditionnelle doit être évidemment mentionnée dans la séquence de compression Comp(.). Remarque : Cette conditionnelle peut être élargie à des cas de produits P « pair presque pur ». On peut désigner par ce terme de «produit pair presque pur ». des produits pairs avec très peu de facteurs impairs. La parfaite connaissance des facteurs impairs permet de se ramener à un cas de produit pair pur. Application en base 10 : La PHASE0,134 cases supplémentaires,NBe;ph3,Be;ph3 nécessitent 157 bits de codage ( 13 + 134 +10 = 157 ). Il faut réserver 477 bits pour le codage ( Type PHASE2 ) si P pair. Il reste donc 134 bits libres ( 768 – ( 157+477 ) ) avec 134 = 13 x 10 + 4. On peut donc se ramener au cas « P pair pur » tant que les facteurs (cases) impairs sont inférieurs ou égal à 13,ces cases impaires doivent être codées chacune sur 10 bits. oooooooooooooooooooo Bits neutres en PHASE3 Rappels :En base 10 et PHASE3, il reste 107 bits neutres à utiliser pour des simplifications et améliorations de codage. Ces bits peuvent être utilisés de différentes façons sachant que : 1) Le codage d'une case déterminée nécessite un seul bit. Exemple : Coder la case C100 codage par le bit qui l'occupe. 2) Le codage d'une case particulière mais aléatoire nécessite 10 bits. Exemple : Coder la première case de Be codage par 10 bits nécessaire (case aléatoire). 3) Le codage d'un nombre particulier de cases peut nécessiter 9 bits. Exemple : Coder le nombre de cases paires de Be 0 ≤ Nombre cases paires ≤ 481 9 bits. Cases qui se décompose sur 4 NP ( 22 cases ). Exemple : C210 = x x x Cases qui dans leurs décompositions ont des exposants peu répétés ( exposants forts ). Exemple : C961 = seule case avec NP11 = 31 au carré. Exemple : C343 = et C686 = x , deux seules cases avec NP4 = 7 au cube. Exemple : C256 = et C768 = x Si codage, on peut en déduire que NP1= 2 se trouvera au maximum à l'exposant 7. La connaissance de ces cases permet ( non de gagner des bits de compression ) mais de mieux cerner la forme et le numéro du produit, en compression et décompression. D'autres cas de codage de cases sont possibles. On peut privilégier le fait de coder des nombres de cases ou des cases particulières sur 1 bit. Coder le nombre de cases paires permet de savoir combien de fois le NP1 = 2 apparaît. On peut de plus en déduire le nombre de cases impaires ( NBe – Nombre de cases paires ). Coder le nombre de cases qui se codent sur 1 seul NP, et / ou 2 NP. Si on suppose que les cases sur 4 NP sont connues, on peut en déduire le nombre de cases qui se codent sur 3 NP ( NBe – ( Nombre cases sur 1 et 2 NP ) ). On peut privilégier le fait de coder plus précisément des NP particuliers. Par exemple, renseigner au maximum les plus présents en terme de probabilité, soit les 4 premiers NP( 2;3;5;7 ). Il est possible de mélanger les différentes approches sans dépasser le quota de 107 bits en Base10. Remarques : Le nombre de bits neutres augmente avec la base. En bases 20 et 30, le nombre de bits neutres est conséquent, en particulier si on se limite à un taux de compression de 50%. oooooooooooooooooooo Compléments sur les combinaisons On va simplement rappeler quelques formules mathématiques pouvant être utiles dans la programmation des combinaisons. Combinaisons Formules de passage n constant ; C( k;n ) = = > C( k+1;n ) Incrémentation de (+1) sur k : C( k+1;n ) = x C( k;n ) = Pck( n;+1) x C ( k;n ) en notant : Pck(+1) = le coefficient de passage de combinaison pour n fixé et k = = > k+1. C( k+1;n ) = Pck( n;+1 ) x C( k;n ) avec Pck( n;+1 ) = Exemple : n = 10 ; k : 2 = = > 2 + 1 = 3 C(2;10) = 10 x 9 / 1 x 2 = 5 x 9 = 45 C(3;10)= 10 x 9 x 8 / 1 x 2 x 3 = 5 x 3 x 8 = 120 Pc2( 10;+1 ) = = 8 / 3 C(3;10) = 120 = 8 / 3 x 45 = 8 x 15 = 120 = 8 / 3 x C(2;10) k constant C(k;n) = = > C(k;n+1) Incrémentation de (+1) sur n : C( k;n+1 ) = x C( k;n ) = Pcn( k;+1 ) x C( k;n ) en notant : Pcn( +1;k ) = le coefficient de passage de combinaison pour k fixé et n = = > n+1 C( k;n+1 ) = Pck( k;+1 ) x C( k;n ) avec Pcn( k;+1 ) = Exemple : k = 3 ; n : 10 = = > 10 + 1 = 11 C(3;10) = 10 x 9 x 8 / 1 x 2 x 3 = 5 x 3 x 8 = 120 C(3;11) = 11 x 10 x 9 / 1 x 2 x 3 = 11 x 5 x 3 = 165 Pcn( 3;+1 ) = = 11 / 8 C(3;11) = 165 = 11 / 8 x 120 = 11 x 15 = 11 x C(3;10) = 165 Formules de passage généralisées Par répétition d’incrémentations en (+1), on peut généraliser les formules de passage pour des incrémentations à tout ordre (+p). n constant C( k;n ) = = > C( k+p;n ) Pck(n;+p) = x x .... x = Pck( n;+p ) = Exemple : n = 10 ; k = 2 et p = 4 = = > k + p = 2 + 4 = 6 n − k = 10 – 2 = 8 C(2;10) = 45 et C 6;10) = 210 Pc2(10 ; + 4) = = = = et Pc2( 10 ; +4 ) x C( 2;10 ) = x 45 = 14 x 15 = 165 k constant C( k;n ) = = > C (k;n+p ) Pcn( k;+p ) = x x .... x = Pcn( k;+p ) = Exemple : k = 2 ; n = 10 et p = 2 = = > n + p = 10 + 2 = 12 n + 2 – k = 10 + 2 – 2 = 10 C( 2;10 ) = 45 et C( 2;12 ) = 66 Pcn( 2;+2 ) = = C(2;12) = Pcn( 2;+2 ) x C(2;10) = x 45= 11 x 2 x 3 = 66 Remarque : Suivant la programmation utilisée les formules de passage peuvent s'avérer très utiles. oooooooooooooooooooo OPERATIONS en BINAIRE Vu le caractère de compression interne (compression suite binaire en suite binaire ) et vu la grandeur des nombres ( en décimal ), il semble naturel de programmer les calculs en binaire. On va simplement faire quelques remarques. ECRITURE BINAIRE Résultat : Tout entier n non nul peut s'écrire comme une somme de puissances de 2. Dans ce cas ,on peut adopter une notation sous forme de MATRICE LIGNE. Exemples : 1 = 2⁰ ( 0 ) ; 2 = 2¹ ( 1 ) 3 = 2¹ + 2⁰ ( 1 ; 0 ) ( 3 = 2 + 1 ) 4 = 2² ( 2 ) ; 5 = 2² + 2⁰ ( 2 ; 0 ) ( 5 = 4 + 1 ) 11 = 2³ + 2¹ + 2⁰ ( 3 ; 1 ; 0 ) ( 11 = 8 +2 + 1 ) 60 = 2⁵ + 2⁴ + 2³ + 2² ( 5 ; 4 ; 3 ; 2 ) ( 60 = 32 + 16 + 8 + 4 ) Cas général : Soit n entier : n = + + + …... + + ( i ; j ; k ;…. ; l ; m ) avec i > j > k > …. > l > m ≥ 0 ( i ; j ; k ;…. ; l ; m ) seront appelés coefficients binaire de la matrice ligne ( n ). ADDITION BINAIRE ECRITURE MATRICE LIGNE Soient A et B deux entiers de matrices lignes (a ) et ( b ) ; A = ( a ) et B = ( b ) Rappel : A = ( a ) A = et B = ( b ) B = Par définition on posera : A + B = ( a ) + ( b ) = ( a;b ) si a ≠ b A + B = ( a ) + ( b ) = ( a + 1) si a = b Exemple1 : A = ( 3 ) A = 2³ ( = 8 ) B = ( 4 ) B = 2² ( = 4 ) On a 3 ≠ 2 = = > A + B = ( 3;2 ) On vérifie bien que A + B = 8 + 4 = 12 = ( 3;2 ) = 2³ + 2². Exemple2 : A = ( 3 ) A = 2³ ( = 8 ) B = ( 3 ) B = 2³ ( = 8 ) On a 3 = 3 = = > A + B = ( 3 + 1 ) = ( 4 ) On vérifie bien que A + B = 8 + 8 = 16 = ( 4 ) = 2³ + 2³ = 2³ + 1 = 2⁴ Exemple3 : A = ( 4;3 ) A = 2⁴ + 2³ ( = 16 + 8 = 24 ) B = ( 2;1;0 ) B = 2² + 2¹ + 2⁰ ( = 4 + 2 + 1 = 7 ) Tous les coefficients binaires sont différents donc : A + B = ( 4;3 ) + ( 2;1;0 ) = ( 4;3;2;1;0 ) A + B = 24 + 7 = 31 = 16 + 8 + 4 +2 + 1 MULTIPLICATION BINAIRE ECRITURE MATRICE LIGNE Il suffit de transcrire en matrice ligne la règle classique du produit de puissances d'un même nombre par la somme des exposants. x = Dans notre étude : a = 2 ; x = Exemple1 : A = ( 3 ) = 2³ = 8 et B = ( 2 ) = 2² = 4 A x B = ( 3 ) x ( 2 ) = ( 3 + 2 ) = ( 5 ) On vérifie bien que :A x B = 8 x 4 = 32 = 2⁵ = 32 Exemple2 : A = ( 3 ) = 2³ = 8 et B = ( 2;1;0 ) = 2² + 2¹ + 2⁰ = 4 + 2 + 1 = 7 Il suffit d'appliquer les règles d'un développement classique. A x B = ( 3 ) x ( 2;1;0 ) = ( 3 ) x ( 2;1;0 ) = ( 3 + 2; 3+1; 3+0 ) = ( 5;4;3 ) Vérification décimale : A x B = 8 x 7 = 56 = 32 + 16 + 8 = ( 5;4;3 ) Exemple3 : A = ( 5;4;3 ) = 56 et B = ( 3;2 ) = 12 A x B = (5;4;3) x (3;2) = (5;4;3) x (3;2) = ( 5+3; 5+2; 4+3; 4+2; 3+3; 3+2 ) A x B = ( 8; 7; 7; 6; 6; 5 ) Puis on réduit suivant les règles de l'addition. A x B = ( 8; 7; 7; 6; 6; 5 ) = ( 8; 8; 7; 5 ) = ( 9; 7; 5 ) Vérification décimale : A = 56 et B = 12 = => A x B = 56 x 12 = 672 A x B = ( 9;7;5 ) = 512 + 128 + 32 = 672 Généralisation : A = ( a1;a2;…... ;a(k-1);ak ) avec a1 > a2 > ….. > a(k-1) > a k ≥ 0 B = ( b1;b2; …... ;b(j-1);bj ) avec b1 > b2 > ….. > b(j-1) > bj ≥ 0 A x B = ( a1;a2;…...a(k-1);ak ) x ( b1;b2;…...b(j-1);bj ) 1) Distribution des coefficients de A sur les coefficients de B A x B = (a1 +b1;a1+b2;…….;a1+b(j-1);a1+ aj;a2+b1;a2+b2; ……. ;a2+b(j-1);a2+ aj; …… ; a(k-1)+b1;a(k-1)+b2; …… ;a(k-1)+b(j-1);a(k-1)+ aj; ak +b1;ak+b2; ……. ;ak+b(j-1);ak+ aj) Remarque : On a ( k x j ) coefficients, somme des coefficients. 2) Réduction et simplification du produit On réduit et simplifie le produit au maximum grâce à l'addition définie précédemment. On obtient un produit avec des coefficients binaires tous différents ( au maximum k x j ). oooooooooooooooooooo FIN ANNEXE On va conclure par les « Revendications » suivi de l’« Abrégé ». Procédé de compression informatique Caractérisé en ce que Il compresse le code binaire source du fichier numérique à compresser, après découpage en base b c’est-à-dire découpage en suites de bits, b nombre entier naturel. Procédé de compression informatique Caractérisé en ce que Il compresse une suite binaire de bits, b nombre entier naturel supérieur ou égal à 8,en une autre suite binaire de longueur inférieure ( bits ). Procédé de compression informatique Caractérisé en ce que Il compresse tous les fichiers informatiques numérisés sans considération de forme, parfaitement sans perte. Procédé de compression informatique Caractérisé en ce que Il compresse tout fichier informatique de poids quelconque en un fichier de poids pouvant être fixé préalablement ( Poids minimum de l'ordre de 50 Ko ), ce qui confère un taux de compression théorique infini au procédé de compression informatique. Procédé de compression informatique Caractérisé en ce que Il compresse une suite binaire de bits, b nombre entier naturel, en étudiant les cases de présence d'un bit appelé « Bit d'étude » noté Be. Procédé de compression informatique Caractérisé en ce que Il se divise en 4 phases, chaque phase n'utilisant que des opérations arithmétiques. Procédé de compression informatique Caractérisé en ce que La phase0 initialise les trois autres phases par coupures du fichier originel en suites de bits et détermination du « Bit d'étude » Be et de son nombre de présence NBe. Procédé de compression informatique Caractérisé en ce que La phase1 code simplement les cases de présence du « Bit d'étude » Be. Procédé de compression informatique Caractérisé en ce que La phase 2 code les cases de présence du « Bit d'étude » Be par leur unique numéro de combinaison. Procédé de compression informatique Caractérisé en ce que La phase3 code les cases de présence du « Bit d'étude » Be par leur unique numéro de produit, produit exprimé en décomposition de facteurs premiers.