Boolean Multiplexer in Practice

Introduction

There are two popular types of problems for evaluating learning classifier systems:

  • single-step - like "question-answer" systems,
  • multi-steps - problems where multiple consequential steps are needed to solve it. Most popular are different kind of mazes (in literature often referred as various kind of MAZE or WOODS environments).

This article will focus on a method for testing single-step systems, where the environment has the Markov property (each state is independent of it's predecessor).

A method referred as boolean multiplexer function will be first described, followed by some examples and a simple Python implementation.

Enter ...

Multiplexer

First, let's gain some intuition about the idea of a multiplexer:

Multiplexing is the generic term used to describe the operation of sending one or more analog or digital signals over a common transmission line at different times or speeds. [source]

In the following scheme, an example of the 4-1 multiplexer with 4 inputs, 2 control signals, and 1 output is presented. The output Q can be one of the input signal A, B, C or D depending on the value of a and b.

There are of course many different configuration options available but this knowledge should be sufficient for now.

Boolean multiplexer function

Boolean multiplexer is a case where each signal is represented in binary using either 0 or 1.

There is a convention that the incoming signal consists of two, concatenated parts - control and data bits

In the example, above we are dealing with 6-bit boolean multiplexer. First 2 bits are capable of addressing 4 inputs ( 2^2 = 4 ) that came along.

The output is a data bit at a location specified by converting control bit number into decimal (in this case bin(01) = dec(1)). Data bits indexing starts from zero.

Examples

Below you will find three examples of multiplexer functions.

3-bit

Control bits: 1, Data bits: 2

The output is the 0-th data bit.

6-bit

Control bits: 2, Data bits: 4

The output is the 3-rd data bit.

11-bit

Control bits: 3, Data bits: 8

The output is the 5-th data bit.

Implementation

The following implementation generates a random binary signal (user needs to provide a number of control bits), and prints the correct value of the signal.

Mind that you need to make sure the bitstring module is available in your OS.

Here is an example of using 2 bits for controlling the signal (6-bit multiplexer):