class Bliftax::Implicant

A class that represents an implicant of a gate.

Constants

SHARP_TABLE

Look-up tables for the sharp operator.

@example

+---+---+---+---+
|A/B| 0 | 1 | - |
+---+---+---+---+
| 0 | E | N | E |
+---+---+---+---+
| 1 | N | E | E |
+---+---+---+---+
| - | 1 | 0 | E |
+---+---+---+---+

bit_result = SHARP_TABLE[a.bit][b.bit]
STAR_TABLE

Look-up tables for the star operator.

@example

+---+---+---+---+
|A/B| 0 | 1 | - |
+---+---+---+---+
| 0 | 0 | N | 0 |
+---+---+---+---+
| 1 | N | 1 | 1 |
+---+---+---+---+
| - | 0 | 1 | - |
+---+---+---+---+

bit_result = STAR_TABLE[a.bit][b.bit]

Attributes

inputs[R]
output[R]

Public Class Methods

make_dummy(inputs, output = '1') click to toggle source

Creates a dummy implicant with the given inputs. This is useful when checking if an implicant is equal to what is expected. The input labels are labeled from ‘a’ to ‘z’ then ‘A’ to ‘Z’, and the output label is ‘out’.

@param inputs [String, Array<String>] the input bits. @param output [String] the output bit.

@return [Implicant] an implicant with dummy labels and the bits set to

the given bits.
# File lib/bliftax/implicant.rb, line 318
def self.make_dummy(inputs, output = '1')
  labels = ('a'..'z').to_a + ('A'..'Z').to_a
  in_labels = labels.first(inputs.size)
  input_str = inputs.is_a?(Array) ? inputs.join : inputs
  Implicant.new(in_labels, 'out', format('%s %s', input_str, output))
end
make_null() click to toggle source

Creates a new NULL Implicant.

@return [Implicant] a null Implicant

# File lib/bliftax/implicant.rb, line 328
def self.make_null
  Implicant.new([], Bliftax::EMPTY, Bliftax::EMPTY, true)
end
new(input_labels, output_label, str, is_null = false) click to toggle source
# File lib/bliftax/implicant.rb, line 73
def initialize(input_labels, output_label, str, is_null = false)
  @is_null = is_null

  return if str.empty?

  (input_bits, output_bit) = parse_bits(str)

  fail 'Input bit size mismatch' if input_labels.size != input_bits.size

  @inputs = []
  input_labels.each_with_index do |label, i|
    @inputs << Bit.new(label, input_bits.at(i), Bit::INPUT)
  end

  @output = Bit.new(output_label, output_bit, Bit::OUTPUT)
end

Public Instance Methods

*(rhs)
Alias for: star
==(other) click to toggle source

Checks for equality.

@param other [Object] whatever to compare against

# File lib/bliftax/implicant.rb, line 252
def ==(other)
  @inputs == other.inputs && @output == other.output
end
Also aliased as: eql?
cost() click to toggle source

Returns the cost of this implicant. A cost refers to the size of the cube, meaning how many don’t-cares this implicant has. For example, an implicant ‘1-00’ has a cost of 3, whereas ‘1–0’ has a cost of 2.

@return [Integer] the cost of this implicant.

# File lib/bliftax/implicant.rb, line 223
def cost
  @inputs.size - @inputs.map(&:bit).count(Bit::DC)
end
covers?(other) click to toggle source

Checks if this implicant covers the given implicant. Implicant a covers b if all bit combinations that b can describe can also be described by a.

@param other [Implicant] the implicant to be compared against.

@return [true, false] true if this covers the given implicant, false

otherwise.
# File lib/bliftax/implicant.rb, line 235
def covers?(other)
  fail 'Argument must be an Implicant' unless other.is_a?(Implicant)

  @inputs.zip(other.inputs).each do |a, b|
    return false unless a.bit == b.bit || a.bit == Bit::DC
  end

  true
end
eql?(other)
Alias for: ==
hash() click to toggle source

Returns the hash value of this instance.

@return [Integer] the hash value of this instance.

# File lib/bliftax/implicant.rb, line 260
def hash
  [@inputs, @output].hash
end
minterms() click to toggle source

Finds the possible minterms that this implicant can represent. For example, a bit string of 101 can only represent m_5, but 10- can represent m_4 and m_5.

@return [Set<Integer>] a set of minterms.

# File lib/bliftax/implicant.rb, line 196
def minterms
  set = Set.new

  bits = @inputs.map(&:bit)
  num_dc = bits.count(Bit::DC)
  str = bits.join
  # There are 2**num_dc combinations
  (2**num_dc).times do |i|
    str_copy = str.dup

    # Convert to binary form and pad with 0
    cnt_str = i.to_s(2).rjust(num_dc, '0')
    cnt_str.split('').each do |b|
      str_copy = str_copy.sub(Bit::DC, b)
    end
    set.add(str_copy.to_i(2))
  end

  set
end
null?() click to toggle source
# File lib/bliftax/implicant.rb, line 245
def null?
  @is_null
end
sharp(rhs) click to toggle source

The Sharp-operator. Described in Chapter 4.10.1 in the Fundamentals of Digital Logic with Verilog Design.

A # B = C

where

  • C = A if A_i # B_i = NULL for some i

  • C = NULL if A_i # B_i = EPSILON for all i

  • Otherwise, C = union of A_i = B_i’ (negated) if A_i = x and B_i != x

@param rhs [Implicant] the right hand side of the operation.

@return [Set<Implicant>] Note that the set size could be 1.

# File lib/bliftax/implicant.rb, line 151
def sharp(rhs)
  unless @inputs.size == rhs.inputs.size
    fail 'Two operands must have equal size for sharp operator'
  end
  unless bits_valid?(@inputs.map(&:bit))
    fail 'Bad bit in LHS operand of sharp operator'
  end
  unless bits_valid?(rhs.inputs.map(&:bit))
    fail 'Bad bit in RHS operand of sharp operator'
  end

  result_bits = []
  @inputs.zip(rhs.inputs).each do |a, b|
    result_bits << SHARP_TABLE[a.bit][b.bit]
  end

  # C = A if A_i # B_i = NULL for some i
  return Set.new([self]) if result_bits.any? { |bit| bit == Bit::NULL }

  # C = NULL if A_i # B_i = EPSILON for all i
  result_is_null = result_bits.all? { |bit| bit == Bit::EPSILON }
  return Set.new([Implicant.make_null]) if result_is_null

  # Set of Implicant to return
  result_set = Set.new

  @inputs.zip(rhs.inputs).each_with_index do |(a, b), i|
    # Check for A_i == DC and B_i != DC
    if a.bit == Bit::DC && b.bit != Bit::DC
      copy = @inputs.map(&:bit)
      copy[i] = b.bit == Bit::ON ? Bit::OFF : Bit::ON
      in_labels = @inputs.map(&:label)
      result = Implicant.new(in_labels, @output.label, bit_str(copy))
      result_set.add(result)
    end
  end

  result_set
end
star(rhs) click to toggle source

The Star-operator. As described in Chapter 4.10 in the Fundamentals of Digital Logic with Verilog Design,

A * B = C

where

  • C = NULL if A_i * B_i = NULL for more than one i

  • Otherwise, C_i = A_i * B_i when A_i * B_i != NULL, and C_i = x (don’t care) for the coordinate where A_i * B_i = NULL

@param rhs [Implicant] the right hand side of the operation.

@return [Implicant] the result of the star operation.

# File lib/bliftax/implicant.rb, line 105
def star(rhs)
  # Sanity check
  unless @inputs.size == rhs.inputs.size
    fail 'Two operands must have equal size for *-operator'
  end
  unless bits_valid?(@inputs.map(&:bit))
    fail 'Bad bit in LHS operand of star operator'
  end
  unless bits_valid?(rhs.inputs.map(&:bit))
    fail 'Bad bit in RHS operand of star operator'
  end

  result_bits = []
  @inputs.zip(rhs.inputs).each do |a, b|
    result_bits << STAR_TABLE[a.bit][b.bit]
  end

  result_is_null = result_bits.count(Bit::NULL) > 1
  unless result_is_null
    # C_i = DC if A_i * B_i == NULL
    result_bits.map! { |b| b == Bit::NULL ? Bit::DC : b }
  end

  # Construct a Implicant instance
  Implicant.new(@inputs.map(&:label),
                @output.label,
                bit_str(result_bits),
                result_is_null)
end
Also aliased as: *
to_blif() click to toggle source

Returns the string representation of this implicant.

@return [String] the string representation of this implicant in BLIF

format.
# File lib/bliftax/implicant.rb, line 304
def to_blif
  format '%s %s', @inputs.map(&:bit).join, @output.bit
end
to_s(show = [:input]) click to toggle source

Return the string version of this implicant.

@param show [:input, :output, :labels, Array<:input, :output, :labels>]

what to show. If Array is used, corresponding information is appended.

@return [String] string representation of this implicant.

# File lib/bliftax/implicant.rb, line 270
def to_s(show = [:input])
  show = [show] unless show.is_a?(Array)

  tokens = []

  if show.include?(:labels)
    # Only show the labels
    if show == [:labels]
      return [@inputs.map(&:label), @output.label].join(Bliftax::SPACE)
    end

    if show.include?(:input)
      tokens << 'INPUTS'
      @inputs.each do |b|
        tokens << format('%-8s %s', b.label, b.bit)
      end
    end
    if show.include?(:output)
      tokens << 'OUTPUT'
      tokens << format('%-8s %s', @output.label, @output.bit)
    end

    return tokens.join("\n") + "\n"
  end

  tokens << @inputs.map(&:bit).join if show.include?(:input)
  tokens << @output.bit if show.include?(:output)
  tokens.join(Bliftax::SPACE)
end

Private Instance Methods

bit_str(bits) click to toggle source

Returns the BLIF-style representation of this implicant. This method assumes that the output bit is 1 because BLIF only states combinations that result in output of 1.

@return [String] representation of the bits in this implicant. The

output bit is separated from the input bits by one space.
# File lib/bliftax/implicant.rb, line 378
def bit_str(bits)
  format '%s 1', bits.join
end
bits_valid?(bits) click to toggle source

Checks whether all the bits are either 1, 0, or DC.

@param bits [Array<String>] the bits to be checked.

@return [true, false] true if all the bits are 1, 0, or DC.

# File lib/bliftax/implicant.rb, line 366
def bits_valid?(bits)
  bits.all? do |bit|
    [Bit::ON, Bit::OFF, Bit::DC].any? { |b| bit == b }
  end
end
parse_bits(str) click to toggle source

Parses the bit string and returns the bits for inputs and outputs.

@param str [String] the string representation of the input and output

bits. Input and output bits must be separated by a whitespace.

@return [Array] contains exactly two elements, the first being the input

bits in String and the second being the output bit in String.

@example Parse a String representation of bits.

parse_bits('010 1')
# => [['0', '1', '0'], '1']
# File lib/bliftax/implicant.rb, line 345
def parse_bits(str)
  is_single = str.split(' ').size == 1

  # Constant gate (likely vcc or gnd)
  if is_single
    input_bits = []
    output_bit = str
  else
    # Parse strings that look like "0001 1"
    (input_bits, output_bit) = str.split(' ')
    input_bits = input_bits.split('')
  end

  [input_bits, output_bit]
end