Tableau de Karnaugh en Python

[MSG]

Bonjour ,

Amis électriciens , amis électroniciens , et ceux sur le devenir , qui n'a pas crisé sur l'utilisation du fameux tableau de Karnaugh , que ce soit sur papier ou sur tableur .

Je vous propose donc sur ce fil , la construction du fameux tableau de Karnaugh , en programmation Python , et de partager avec vous ces éventuelles option et amélioration à apporter à celui-ci .

J'ai déjà écrit un code fonctionnel , mais le fait de repartir de zéro me permettra de mieux l'optimiser et donner peut-être envie à certains à se lancer en langage Python , que je découvre comme vous .

Aller au travail !

MSG

[MSG]

Pour commencer , nous avons besoin de définir la liste des variables utilisées dans celui-ci .

On peut simplement les énumérer

Code : Tout sélectionner

#!/usr/bin/python3

var_list = "abcd"     # liste des variables

Soit les générer en accédant au tableau ascii avec les commande ORD et CHR que l'on peut tester dans une console après avoir lancer le programme python .

Code : Tout sélectionner

#!/usr/bin/python3

n = 4             # nombre de variables à créer
var_list = ""
for i in range(n):
   var_list += chr(97+i)

Test


On pourra par la suite modifier l'ordre des variables et voir ce qui se passe .

De cette façon , on peut déterminer les valeurs de chaque variable .

Code : Tout sélectionner

for var in var_list:   
   print( "%s %3i %i %i" %( var, ord(var), ord(var)-97, 2**( ord(var)-97 )))

- son code ascii
- son rang dans un mot binaire
- son poids binaire

[MSG]

Maintenant que l'on a une liste de variables , il faut les répartir en deux groupes pour certaines en abscisses (x) d'autres en ordonnées (y) .

Code : Tout sélectionner

var_x = []
var_y = []
for i in range( len( var_list )):
   if i%2: var_y += var_list[i]
   else:   var_x += var_list[i]

print ("%s\n%s\n%s" %( var_list, var_x, var_y ))

Que se passe t-il avec un nombre de variables impair ?

Code : Tout sélectionner

n = 5             # nombre de variables à créer
var_list = ""
for i in range(n):
   var_list += chr(97+i)

var_x = []
var_y = []
for i in range( len( var_list )):
   if i%2: var_y += var_list[i]
   else:   var_x += var_list[i]

print ("%s\n%s\n%s" %( var_list, var_x, var_y ))

[MSG]

Le tableau de Karnaugh est construit sur la base du code Gray , qui n'autorise qu'un seul bit ne change à chaque passage à une case mitoyenne .
Pour construire cette liste de code Gray , adapté à notre tableau , on va se référer au nombre de variables en abscisses (x) .

Code : Tout sélectionner

gray = []
for i in range( 2**( len( var_x ))):
   gray.append(i ^ i>>1)

print (gray)

Pour l'explication du code Gray , on en a parlé sur cet autre sujet .
viewtopic.php?f=38&t=5680


On va donc pouvoir voir à quoi ressemble le code gray en affectant les bits correspondant à chaque variable suivant sa position dans le tableau .

Code : Tout sélectionner

for i in range( len( var_x )):
   for j in gray:
      var_x[i] += (2**i & j) and "#" or " "

for i in range( len( var_y )):
   for j in gray:
      var_y[i] += (2**i & j) and "#" or " "


for i in var_x: print (i)

for i in var_y: print (i)

On peut voir les variables avant et après affectation , les 1 étant le "#" et les 0 des espaces.



le code a été changé pour faciliter l'affichage ultérieurement .

Code : Tout sélectionner

# Affectation bits gray aux variables
#-------------------------------------
for i in range( len( var_x )):
   for j in gray:
      var_x[i] += (2**i & j) and var_x[i][0].upper() or " "

for i in range( len( var_y )):
   for j in gray:
      var_y[i] += (2**i & j) and var_y[i][0].upper() or " "


for i in var_x: print(i)
print()
for i in var_x: print(i)
print()

[MSG]

Avant d'aller plus loin , il nous faut générer le tableau d'indexation (le gros morceau ) .

Code : Tout sélectionner

# Tableau d'indexation
#---------------------- 
tx = 2**( len( var_x ))    # dimension x
ty = 2**( len( var_y ))    # dimension y
t_index = [[0] * tx]

Code : Tout sélectionner

#
#  calcul ligne
#
for i in var_x :
   for j in range( tx ):
      t_index[0][j] += 2**(ord(i[0].upper())-65) * (i[j+1] != " ")

Code : Tout sélectionner

#
# calcul colonne
#
for j in range(1, ty):
   t_index.append([0] * tx)
   for i in var_y:
      t_index[-1][0] += 2**(ord(i[0].upper())-65) * (i[j+1] != " ")

Code : Tout sélectionner

#
# somme ligne et colonne
#
for i in range(1, ty):
   for j in range(1, tx):
      t_index[i][j] = t_index[i][0] + t_index[0][j]

Code : Tout sélectionner

#
# test
#------
for i in range(ty):
   aff=""
   for j in range(tx):
      aff += "%3s " %t_index[i][j]
   print (aff)

[MSG]

Je me bats avec le code qui semble présenter des erreurs alors qu'il n'y en a pas quand je le lance depuis le fichier où il est stocké (sacré console) .

L'affichage du tableau mis en forme .

Code : Tout sélectionner

# affichage du tableau
#----------------------
aff = "\n"
for i in range( len(var_x)-1, -1, -1 ):
   aff += "%s%s" %( "  "*(len(var_y)),  " ." )
   for j in range( 1, len( var_x[0] )):
      #if j == 0: aff_x += "   "
      aff += "%s." %var_x[i][j]
   aff += "\n"
aff += "%s%s%s\n" %( " ."*len( var_y), " .", " ."*tx )

for i in range( ty ):
   for j in range( tx ):
      if j==0:
         for k in range( len( var_y )-1,-1,-1 ):
            aff += "%s." %var_y[k][i+1]
         if k == 0: aff += " ."
      aff += "%1s." %"?"    #table[i][j]   (de vérité)
   aff +="\n"
print(aff)

On peut donc l'agrandir autant qu'on veut , seul l'affichage posera problème suivant l'écran . un 10 variables ci-dessous !!!

[MSG]

Revenons à un tableau plus raisonnable et ajoutons y une table de vérité avec quelques données .

Le code du débit à été modifier comme suit .

Code : Tout sélectionner

# liste des variables
#---------------------
n = 5                     # nombre de variables à créer
var_list = ""
for i in range(n):
   var_list += chr(97+i)

# table de verité
#------------------
table = [0] * 2**n
table[10] = 1
table[18] = 1
table[5] = True

La fin du code est modifiée pour ajouter le tableau .

Code : Tout sélectionner

# affichage du tableau
#----------------------
aff = "\n"
for i in range( len(var_x)-1, -1, -1 ):
   aff += "%s%s" %( "  "*(len(var_y)),  " ." )
   for j in range( 1, len( var_x[0] )):
      #if j == 0: aff_x += "   "
      aff += "%s." %var_x[i][j]
   aff += "\n"
aff += "%s%s%s\n" %( " ."*len( var_y), " .", " ."*tx )

for i in range( ty ):
   for j in range( tx ):
      if j==0:
         for k in range( len( var_y )-1,-1,-1 ):
            aff += "%s." %var_y[k][i+1]
         if k == 0: aff += " ."
      aff += "%1s." %int( table[ t_index[i][j] ])  # de vérité
   aff +="\n"
print(aff)

ce qui donne le résultat suivant .


J'oubliais , j'ai rajouté à l'affichage de la table d'index pour montrer que les bits sont bien placés au bon endroit .

Code : Tout sélectionner

# tableau index
#--------------
aff_index = ""
for i in range( len( t_index )):
   for j in range( len( t_index[0] )):
      aff_index += "%3i " %t_index[i][j]
   aff_index += "\n"
print (aff_index)

[MSG]

Permutons l'ordre des variables dans le tableau .

Code : Tout sélectionner

# table de verité
#------------------
table = [0] * 2**n
table[10] = 1
table[18] = 1
table[5] = True

# Permutations des variables
#------------------------------
var_list = "dceab"

et comparons .

Pourquoi permuter ? me direz-vous .

Si on prend par exemple la valeur 15 , on voit qu'elle est mitoyenne avec 7, 11, 13 et 14 .
Mais , suivant la taille et le nombre de variables il peut y en avoir beaucoup plus .
Dans notre cas , 15 = 01111 est mitoyen avec la liste ci-dessous .

Code : Tout sélectionner

# Permutations des variables
#------------------------------
var_list = "abced"

[MSG]

Aller la petite cerise sur le gâteau pour finir (pour ce soir).

Remplir le tableau est résolu , reste que la table de vérité , n'est pas une mince affaire , si l'on a des équations .
Ma solution , mais peut-être y a t-il autre façon de faire .

Pour trouver toutes les cases d'une variable donnée , par exemple B=1 :
Je déclare mes variables et j'utilise l'opération test : bool( i&B ) ou int( bool( i&B )) si je veux du binaire .


Pour trouver toutes les cases de son contraire B\ (barre) , j'utilise l'opération test : bool( i&B!=B ) ou int( bool( i&B!=B )) si je veux du binaire .
On peut l'écrire aussi ainsi : bool( i&B^B ) ou int( bool( i&B^B )) . Remplacer le != par ^ , ça fait une touche en moins à taper .

[MSG]

On complique avec l'équation B mais pas C , soit bool( i&B and i&C!=C)


On rajoute à l'équation qu'on ne veut pas A non plus , soit bool( i&A!=A and i&B and I&C!=C


Une autre , je veux E , bool( i&A!=A and i&B and I&C!=C and i&E


Il n'en reste plus que deux au choix D ou pas D , je choisi la seconde , pas de D , soit bool( i&A!=A and i&B and I&C!=C and i&E and i&D!=D


A=0, B=1, C=0, D=0, D=1 donne 10010 = 18 , c'est la bonne .