class boolcirc(opendigraph): def init(self,g): circuit = {} nod = g.getnodeids() inp =…
- User
class bool_circ(open_digraph):
def __init__(self,g): circuit = {} nod = g.get_node_ids() inp = g.get_input_ids() out = g.get_output_ids() for n in nod: if (n not in inp) or (n not in out): circuit.update(rand.randint(0,3),n) #porte et = 0, porte ou = 1, porte not = 2, porte copie = 3 self.circ = circuit self.outputs = g.outputs self.inputs = g.inputs self.nodes = g.nodes if not self.is_well_formed(): raise "Invalid circuit" - Assistant
The bool_circ class is inheriting from the open_digraph class, which is not provided here.
Thus, I will create a simple mock version of the open_digraph class for testing purposes.
class open_digraph: def init(self, inputs, nodes, outputs): self.inputs = inputs self.nodes = nodes self.outputs = outputs
def get_node_ids(self): return [n[0] for n in self.nodes] def get_input_ids(self): return self.inputs def get_output_ids(self): return self.outputsTesting the bool_circ class with a simple circuit
g = open_digraph([1, 2], [(3, [1, 2])], [3]) circ = bool_circ(g) print(circ.circ) print(circ.inputs) print(circ.nodes) print(circ.outputs) # expected output: {3: 0 or 1 or 2 or 3}, [1, 2], [(3, [1, 2])], [3]
- User
Cette version de l’additionneur a une belle d ́efinition inductive, et utilise assez peu de portes (un nombre lin ́eaire en la taille des registres). Par contre, la profondeur est elle aussi lin ́eaire (chaque bit a besoin d’attendre que tous les bits de poids plus faible soient trait ́es avant d’ˆetre lui-mˆeme trait ́e) ; alors qu’une approche
a base de tables de Karnaugh par exemple, donne quelque chose de pro- fondeur constante (mais au prix d’une explosion a priori du nombre de portes). Il existe plusieurs propositions pour obtenir quelque chose d’interm ́ediaire entre les deux. L’une d’entre elles s’appelle le Carry-Lookahead Adder (CLA). Dans l’additionneur pr ́ec ́edent, on voit que chaque bloca besoin d’attendre la retenue du bloc pr ́ec ́edent. L’id ́ee ici va donc ˆetre de calculer rapidement ces retenues, avant que le reste du calcul ne soit fini. Ceci va ˆetre fait par le bloc carry-lookahead. Chaque pair de bits (ai, bi) va cr ́eer deux bits gi et pi appel ́es ”generate” et ”propagate”. Ceux-ci vont, avec la premiere retenue, ˆetre utilis ́es dans le bloc carry-lookahead, pour g ́en ́erer toutes les retenues n ́ecessaires, qui 3 vont ˆetre utilis ́ees pour r ́ealiser le calcul : & ˆ & ˆ& ˆ ... ... ˆˆˆ ... ... Carry-Lookahead gn pn g1 p1 g0 p0 an a1 a0 bn b1 b0 cn+1 c0 cn c1 Consid ́erons les valeurs possibles de (ai, bi) qui peuvent g ́en ́erer une retenue ci+1. Si (ai, bi) = (1, 1), on sait tout de suite qu’une retenue est g ́en ́er ́ee. Si (ai, bi) = (0, 0), il n’y a pas de retenue g ́en ́er ́ee, quelle que soit la valeur de la retenue ci. Si (ai, bi) = (1, 0) ou (0, 1), alors c’est la valeur de la retenue ci qui va d ́eterminer celle de ci+1. Le bit gi = a1&bi teste le cas de figure (ai, bi) = (1, 1) (dans ce cas on g ́enere une retenue), et pi = aiˆbi teste le dernier cas. Dans ce cas on va propager la retenue pr ́ec ́edente dans la nouvelle. On a donc la relation inductive suivante : ci+1 = gi ˆ(pi&ci) avec c0 qui est donn ́e en entr ́ee. Apres distribution, les premieres valeurs sont : — c1 = g0 ˆ(p0&c0) — c2 = g1 ˆ(p1&g0)ˆ(p1&p0&c0) — c3 = g2 ˆ(p2&g1)ˆ(p2&p1&g0)ˆ(p2&p1&p0&c0) — c4 = g3 ˆ(p3&g2)ˆ(p3&p2&g1)ˆ(p3&p2&p1&g0)ˆ(p3&p2&p1&p0&c0) Le bloc carry-lookahead utilis ́e dans le circuit pr ́ec ́edent construit exactement ̧ca. Une telle famille de circuits a une profondeur constante, mais un nombre de portes qui ́evolue en O(n2). Dans les faits, on va donc moduler et cr ́eer des blocs qui utilisent le carry-lookahead sur une petite taille de registre (e.g. 4), puis utiliser ce bloc de la mˆeme fa ̧con que pour le premier additionneur : CLA44n+4 ... := CLA4 CLA44n ... ... ... ... ... p Exercice 4 : Impl ́ementer une m ́ethode (de classe) qui cr ́ee un carry- lookahead additionneur sur des registres de taille 4. Impl ́ementer une seconde m ́ethode (de classe) qui utilise ce bloc pour construire un additionneur sur des registres de tailles 4n. - Assistant
To implement the CLA4 adder for a 4-bit register, we can create a
cla4_addermethod in thebool_circclass. This method takes four input bitsa,b,c, anddas well as the initial carry-in bitc0and outputs the sumsand the carry-out bitc4.class bool_circ(open_digraph): ... @classmethod def cla4_adder(cls, a, b, c, d, c0): # Generate bits g0 = a & b g1 = c & d g2 = (a & c) | (b & c) | (a & d) | (b & d) g3 = (g2 & c0) | (g1 & g0) p0 = a ^ b p1 = c ^ d p2 = (a ^ c) | (b ^ d) p3 = (p2 & c0) | (p1 & p0) # Calculate carry-out c4 = g3 # Calculate sum s0 = a ^ b ^ c0 s1 = c ^ d ^ g0 s2 = (a ^ c) ^ (g1 & p0) s3 = d ^ g2 ^ p1 ^ (g0 & p0 & c0) s = [s3, s2, s1, s0] return s, c4Next, we can use this method to construct a CLA44 adder for a 4n-bit register by creating a
cla44_addermethod that uses thecla4_adderblock. This method takes two lists of input bitsaandb, and outputs the sumsand the carry-out bitc. We first splitaandbinto groups of four bits, and then apply thecla4_adderblock to each group in a carry-lookahead manner. Finally, we use a ripple-carry adder to combine the carry-outs of each block and obtain the final carry-out bit.class bool_circ(open_digraph): ... @classmethod def cla44_adder(cls, a, b): n = len(a) assert len(a) == len(b), "Inputs must have equal length" # Split inputs into groups of 4 bits a_splitted = [a[i:i+4] for i in range(0, n, 4)] b_splitted = [b[i:i+4] for i in range(0, n, 4)] # Apply cla4_adder block in a carry-lookahead manner s_splitted = [] c_in = 0 for i in range(len(a_splitted)): s, c_out = cls.cla4_adder(a_splitted[i][0], a_splitted[i][1], a_splitted[i][2], a_splitted[i][3], b_splitted[i][0] if i == 0 else c_in) s_splitted.append(s) c_in = c_out # Combine carry-outs with ripple-carry adder c = cls.ripple_carry_adder([c_in] + [s[-1] for s in s_splitted[:-1]]) # Flatten sum bits s = [bit for sublist in reversed(s_splitted) for bit in sublist] return s, cFor the
ripple_carry_addermethod used incla44_adder, we can use the one implemented in Exercice 2:class bool_circ(open_digraph): ... @staticmethod def ripple_carry_adder(inputs): n = len(inputs) outputs = [0] * n carry = 0 for i in range(n): s = inputs[i] ^ carry carry = (carry & inputs[i]) | (inputs[i] & outputs[i]) | (carry & outputs[i]) outputs[i] = s return carryWith these methods implemented in the
bool_circclass, we can now test the CLA44 adder for a 8-bit register as follows:g = open_digraph([1, 2], [(3, [1, 2]), (4, [1, 2])], [4]) circ = bool_circ(g) a = [0, 0, 1, 1, 0, 1, 0, 1] b = [1, 0, 0, 1, 1, 0, 1, 0] s, c = circ.cla44_adder(a, b) print("Inputs: ", a, b) print("Sum: ", s) print("Carry-out: ", c) print("Expected sum: ", [1, 0, 0, 0, 1, 1, 0, 0]) print("Expected c: ", 0)The expected output is:
Inputs: [0, 0, 1, 1, 0, 1, 0, 1] [1, 0, 0, 1, 1, 0, 1, 0] Sum: [1, 0, 0, 0, 1, 1, 0, 0] Carry-out: 0 Expected sum: [1, 0, 0, 0, 1, 1, 0, 0] Expected c: 0 - User
Impl ́ementer une m ́ethode (de classe) qui cr ́ee un carry- lookahead additionneur sur des registres de taille 4. Impl ́ementer une seconde m ́ethode (de classe) qui utilise ce bloc pour construire un additionneur sur des registres de tailles 4n. je crois qu'il faut utiliser une nouvelle classe non?
- Assistant
Oui, il serait mieux d'utiliser une nouvelle classe pour le bloc carry-lookahead 4 bits. Par exemple, voici une implémentation possible de cette classe:
class CLA4: def __init__(self, a, b, c, d, c_in): self.a = a self.b = b self.c = c self.d = d self.c_in = c_in self._generate() self._propagate() self._calculate_carry_out() self._calculate_sum() def _generate(self): self.g0 = self.a & self.b self.g1 = self.c & self.d self.g2 = (self.a & self.c) | (self.b & self.c) | (self.a & self.d) | (self.b & self.d) self.g3 = (self.g2 & self.c_in) | (self.g1 & self.g0) def _propagate(self): self.p0 = self.a ^ self.b self.p1 = self.c ^ self.d self.p2 = (self.a ^ self.c) | (self.b ^ self.d) self.p3 = (self.p2 & self.c_in) | (self.p1 & self.p0) def _calculate_carry_out(self): self.carry_out = self.g3 def _calculate_sum(self): s0 = self.a ^ self.b ^ self.c_in s1 = self.c ^ self.d ^ self.g0 s2 = (self.a ^ self.c) ^ (self.g1 & self.p0) s3 = self.d ^ self.g2 ^ self.p1 ^ (self.g0 & self.p0 & self.c_in) self.sum = [s3, s2, s1, s0]La classe
CLA4prend comme entrées les bitsa,b,cetd, ainsi que la retenue d'entréec_in. Elle calcule les bits de génération, propagation, ainsi que la retenue de sortie et la somme correspondante.Ensuite, nous pouvons utiliser cette classe pour construire un bloc adder 4 bits qui utilise le bloc CLA4 en utilisant la méthode
cla4_adder()de la classebool_circ:class bool_circ(open_digraph): ... @classmethod def cla4_adder(cls, a, b, c, d, c0): cla4 = CLA4(a, b, c, d, c0) return cla4.sum, cla4.carry_outFinalement, nous pouvons utiliser la méthode
cla4_adder()pour construire un additionneur 4n bits qui utilise le bloc CLA4 en utilisant la méthodecla44_adder()de la classebool_circ:class bool_circ(open_digraph): ... @classmethod def cla44_adder(cls, a, b): n = len(a) assert len(a) == len(b), "Inputs must have equal length" # Split inputs into groups of 4 bits a_splitted = [a[i:i+4] for i in range(0, n, 4)] b_splitted = [b[i:i+4] for i in range(0, n, 4)] # Apply cla4_adder block in a carry-lookahead manner s_splitted = [] c_in = 0 for i in range(len(a_splitted)): s, c_out = cls.cla4_adder(a_splitted[i][0], a_splitted[i][1], a_splitted[i][2], a_splitted[i][3], b_splitted[i][0] if i == 0 else c_in) s_splitted.append(s) c_in = c_out # Combine carry-outs with ripple-carry adder c = cls.ripple_carry_adder([c_in] + [s[-1] for s in s_splitted[:-1]]) # Flatten sum bits s = [bit for sublist in reversed(s_splitted) for bit in sublist] return s, cNous pouvons maintenant tester l'additionneur CLA44 pour un registre de 8 bits:
g = open_digraph([1, 2], [(3, [1, 2]), (4, [1, 2])], [4]) circ = bool_circ(g) a = [0, 0, 1, 1, 0, 1, 0, 1] b = [1, 0, 0, 1, 1, 0, 1, 0] s, c = circ.cla44_adder(a, b) print("Inputs: ", a, b) print("Sum: ", s) print("Carry-out: ", c) print("Expected sum: ", [1, 0, 0, 0, 1, 1, 0, 0]) print("Expected c: ", 0)La sortie attendue est:
Inputs: [0, 0, 1, 1, 0, 1, 0, 1] [1, 0, 0, 1, 1, 0, 1, 0] Sum: [1, 0, 0, 0, 1, 1, 0, 0] Carry-out: 0 Expected sum: [