A Quantum Engineering Focused Linux Distro From Scratch — Day 13

I put the distro (pre source download) up on github @ https://github.com/comp-phys-marc/quantum-linux and already got one GitHub ★. Having the updater script helped the root fit in a github repo without my having to use git lfs (large file storage — not to be confused with Linux From Scratch).

Where I left off on the transpiler side of things, the task of typing out bit-wise combinational logic using the PhysicalExpression::Add and PhysicalExpression::Mul structs seemed dire, especially for the larger data types.

So, I started putting together some tooling to help me with this. I noticed a few connections between the task I had to do and group theory. Namely, the numbers I was working with were all modulo n since they all existed within data type size limitations. Second, I would want to synthesize combinational representations of individual operations like u64.mul and u64.add. These each defined an operation between numbers — members of a group of numbers modulo n — that brought two numbers in the group to another number in the group. Or read, of the same data type.

I had a basic group implementation in Python kicking around.

class Group:

    def __init__(self, operation, members, identity) -> None:
        if operation is not None:
            self.operation = operation
        else:
            raise ValueError("A composition operation must be provided with a Group.")
        if identity is not None:
            self.identity = identity
        else:
            raise ValueError("An identity element must be provided with a Group.")
        if isinstance(members, list):
            self.members = []
            for pair in members:
                if not (isinstance(pair, list) and len(pair) == 2) \
                    or self.operation(*pair) != self.identity \
                        or self.operation(*pair.reverse()) != self.identity:
                    raise ValueError("Group members must be provided in pairs of inverses.")
                if self.operation(pair[0], self.identity) != pair[0] \
                    or self.operation(pair[1], self.identity) == pair[1]:
                    raise ValueError("Group members composed with the identity must not change.")
                self.members += pair

class Abelian(Group):

    def __init__(self, operation, members, identity) -> None:
        super().__init__(operation, members, identity)
        self.commutative = True

I added a method to generate a table of compositions. Think truth tables from digital logic, only more abstract.

def generate_table(self):
    self.table = {}

    if self.commutative:
        for [first, second] in itertools.combinations(self.members, 2):
            res = self.operation(first, second)
            self.table[res] = [first, second]
    else:
        for [first, second] in itertools.permutations(self.members, 2):
            res = self.operation(first, second)
            self.table[res] = [first, second]

I realized that in order to generate a truth table for a u64.mul instruction, for example, I would have to know the mod inverses of every number between 0 and 18446744073709551615 to use the existing code. So, I relaxed the constraints on the Group by creating a PseudoGroup that could be used to find mod n inverses x of numbers y such that y * x = 1 mod n by brute force instead of by use of the extended euclidean algorithm.

class PseudoGroup:
    """
    Relaxes the constraints of a Group. Useful for solving mod n 
    inverses so that a proper Group can be constructed next.
    """

    def __init__(self, operation, members, identity) -> None:
        if operation is not None:
            self.operation = operation
        else:
            raise ValueError("A composition operation must be provided with a Group.")
        if identity is not None:
            self.identity = identity
        else:
            raise ValueError("An identity element must be provided with a Group.")
        if isinstance(members, list):
            self.members = members

        self.commutative = None
        self.table = {}

I added a Binary PseudoGroup to help me with my circuit synthesis, complete with a truth table generation method that was could handle different bit lengths.

class Binary(PseudoGroup):

    def __init__(self, operation, members, identity, data_type=None, symbol="o") -> None:
        super().__init__(self, operation, members, identity)

        self.data_type = data_type
        self.symbol = symbol
        self.expressions = []
        self.minterms = []

    def generate_table(self):
        self.table = {}

        def save_with_type(res, first, second):
            if self.data_type == "I8":
                self.table["{0:08b}".format(res)] = ["{0:08b}".format(first), "{0:08b}".format(second)]
            elif self.data_type == "I32":
                self.table["{0:32b}".format(res)] = ["{0:32b}".format(first), "{0:32b}".format(second)]
            elif self.data_type == "I64":
                self.table["{0:64b}".format(res)] = ["{0:64b}".format(first), "{0:64b}".format(second)]

            # TODO: support more data types

        if self.commutative:
            for [first, second] in itertools.combinations(self.members, 2):
                res = self.operation(first, second)
                if not self.data_type:
                    self.table[res] = [first, second]
                else:
                    save_with_type(res, first, second)
        else:
            for [first, second] in itertools.permutations(self.members, 2):
                res = self.operation(first, second)
                if not self.data_type:
                    self.table[res] = [first, second]
                else:
                    save_with_type(res, first, second)

I put together a very simple brute-force approach to constructing SOP (Sum of Product) boolean expressions for each of the bits in the truth tables. Check out the repo for the logic simplification helper method’s source — it’s a bit long.

    def synthesize_logic(self, simplify=False, verbose=False):
        if self.data_type == "I32":
            expressions = [[] for p in range(32)]
            minterms = [[] for p in range(32)]
        elif self.data_type == "I64":
            expressions = [[] for p in range(64)]
            minterms = [[] for p in range(64)]
        elif self.data_type == "I8":
            expressions = [[] for p in range(8)]
            minterms = [[] for p in range(8)]

        # TODO: support more data types

        for (res, operands) in self.table.items():
            for p in range(len(res)):
                if res[p] == "1":
                    boolean_exp = ""
                    j = -1
                    for o in range(2):
                        label = "b"
                        if o == 0:
                           label = "a"
                        for b in operands[o]:
                            j += 1
                            o_bit = f" {label}{j}"
                            if b == "1":
                                if boolean_exp != "":
                                    boolean_exp += f" * {o_bit}"
                                else:
                                    boolean_exp += o_bit
                    if not boolean_exp in expressions[p]:
                        expressions[p].append(boolean_exp)
                        minterms[p].append("".join(operands))

        if verbose:
            for i in range(len(expressions)):
                perm_bit = "c{i} ="
                perm_bit_exps = expressions[i]
                perm_bit_total_exp = perm_bit + " + ".join(perm_bit_exps)
                print(perm_bit_total_exp)

        if simplify:
            expressions, minterms = self._simplify_logic(expressions, minterms, verbose)
        
        self.expressions = expressions
        self.minterms = minterms

With this in place I could write short scripts to generate the tables and calculate expressions for data types. Here are examples for I32 and u64.

u64 operations

def mul(first, second):
    return int("{0:64b}".format(first * second), 2)

def add(first, second):
    return int("{0:64b}".format(first + second), 2)

I32 operations

def mul(first, second):
    res = first * second
    magnitude = "{0:31b}".format(res)
    if res < 0:
        return - int(magnitude, 2)
    else:
        return int(magnitude, 2)

def add(first, second):
    res = first + second
    magnitude = "{0:31b}".format(res)
    if res < 0:
        return - int(magnitude, 2)
    else:
        return int(magnitude, 2)

u64 members

members = []

# the maximum 64 bit unsigned integer
for member in range(18446744073709551615):
    members.append(member)

I32 members

members = []

for member in range(-2147483647, 2147483647):
    members.append(member)

u64 class usage

multiplicative_group = Binary(
    mul, 
    members,
    1, 
    data_type="u64", 
    symbol="*"
)

additive_group = Binary(
    add, 
    members,
    1, 
    data_type="u64", 
    symbol="+"
)

multiplicative_group.generate_table()
additive_group.generate_table()

multiplicative_group.synthesize_logic(verbose=True, simplify=True)
additive_group.synthesize_logic(verbose=True, simplify=True)

I32 class usage

multiplicative_group = Binary(
    mul, 
    members,
    1, 
    data_type="I32", 
    symbol="*"
)

additive_group = Binary(
    add, 
    members,
    1, 
    data_type="I32", 
    symbol="+"
)

multiplicative_group.generate_table()
additive_group.generate_table()

multiplicative_group.synthesize_logic(verbose=True, simplify=True)
additive_group.synthesize_logic(verbose=True, simplify=True)

I ran the I32 script to generate some expressions but ran into a random debugger disconnection error after an hour of building out the members list.

I realized I might have to improve the implementation for performance. Of course, the synthesis would have to be improved anyhow. I didn’t take digital electronics in university for nothing and could do better than brute force. I had also begun to collect papers that discussed particular implementations of these operations.