Logical minimization of multilevel coded functions

Mir M. Mirsalehi and Thomas K. Gaylord

Author Affiliations

Mir M. Mirsalehi^{1,}^{2} and Thomas K. Gaylord^{1}

^{1}When this work was done, both authors were with Georgia Institute of Technology, School of Electrical Engineering, Atlanta, Georgia 30332. USA

^{2}Mir M. Marsalehi is now with the University of Alabama in Huntsville, Department of Electrical and Computer Engineering, Huntsville, Alabama 35899.

Discrete numerical values in digital processing systems may be encoded in two-level (binary) or higher-level (multilevel) representations. Multilevel coding can produce smaller and more efficient processors. In truth-table lookup processing, the number of entries (reference patterns) can be reduced using multilevel coding. Since parallel-input/parallel-output optical truth-table lookup processors can be constructed based on holographic content-addressable memories, it is essential to know the minimum storage required to implement various functions. A new simple method for reducing multivalued functions is presented. This method is based on an extension of the Quine-McCluskey minimization method used for binary logic functions. This minimization method is then applied to the truth tables representing (1) modified signed-digit addition, (2) residue addition, and (3) residue multiplication. A programmable logic array gate configuration for the modified signed-digit adder is presented.

You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

You do not have subscription access to this journal. Article level metrics are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Truth Tables Corresponding to the Transfer (T and T^{1}) and Weight (Wand W^{1}) Functions Used In the MSD Adder

X

Y

T

W

T^{1}

W^{1}

$\overline{1}$

$\overline{1}$

$\overline{1}$

0

$\overline{1}$

0

$\overline{1}$

0

$\overline{1}$

1

0

$\overline{1}$

$\overline{1}$

1

0

0

0

0

0

$\overline{1}$

$\overline{1}$

1

0

$\overline{1}$

0

0

0

0

0

0

0

1

1

$\overline{1}$

0

1

1

$\overline{1}$

0

0

0

0

1

0

1

$\overline{1}$

0

1

1

1

1

0

1

0

Table II

Reduced Reference Patterns that Produce a 1 In the Output Digit z_{n} (n ≠ 0, 1, N) of the MSD Addera

${X}_{\overline{1}1}$

1

X

${X}_{\overline{1}1}$

1

X

0

1

X

0

1

X

${X}_{\overline{1}1}$

X_{01}

1

${X}_{\overline{1}1}$

1

X

0

X_{01}

X_{01}

0

1

X_{01}

$\overline{1}$

$\overline{1}$

X

0

1

X

0

X_{01}

1

0

1

X

${X}_{\overline{1}1}$

1

X

${X}_{\overline{1}1}$

X_{01}

1

${X}_{\overline{1}1}$

$\overline{1}$

X_{01}

0

0

1

$\overline{1}$

0

X

0

0

X

0

1

X

0

X

1

0

1

X_{01}

0

X_{01}

X_{01}

${X}_{\overline{1}1}$

$\overline{1}$

1

0

0

X_{01}

$\overline{1}$

1

X

0

$\overline{1}$

X

0

1

1

0

X_{01}

X

0

$\overline{1}$

X_{01}

${X}_{\overline{1}1}$

0

1

${X}_{\overline{1}1}$

0

X_{01}

0

$\overline{1}$

1

0

$\overline{1}$

X

$\overline{1}$

1

X

0

X_{01}

X

0

1

1

0

$\overline{1}$

1

${X}_{\overline{1}1}$

0

X_{01}

${X}_{\overline{1}1}$

0

1

0

$\overline{1}$

X_{01}

0

1

X

$\overline{1}$

$\overline{1}$

X

${X}_{\overline{1}1}$

1

1

${X}_{\overline{1}1}$

X_{01}

X

0

0

X_{01}

${X}_{\overline{1}1}$

$\overline{1}$

1

${X}_{\overline{1}1}$

X_{01}

X_{01}

${X}_{\overline{1}1}$

1

X_{01}

0

0

X

$\overline{1}$

0

X

${X}_{\overline{1}1}$

X_{01}

X

${X}_{\overline{1}1}$

1

1

0

0

1

${X}_{\overline{1}1}$

$\overline{1}$

X_{01}

${X}_{\overline{1}1}$

1

X_{01}

${X}_{\overline{1}1}$

X_{01}

X_{01}

Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as Y_{n}Y_{n−1}Y_{n−2}X_{n}X_{n−1}X_{n−2}. The digit number of the output starts with n = 0 for the least significant digit and ends with n = N for the most significant digit

Table III

Reduced Reference Patterns that Produce a 1 in the Output Digit z_{1} of the MSD Addera

0

1

$\overline{1}$

$\overline{1}$

$\overline{1}$

$\overline{1}$

0

1

0

0

$\overline{1}$

0

0

X_{01}

0

1

0

$\overline{1}$

$\overline{1}$

1

0

1

0

X_{01}

$\overline{1}$

0

0

0

${X}_{\overline{1}1}$

X_{01}

${X}_{\overline{1}1}$

1

$\overline{1}$

1

0

$\overline{1}$

${X}_{\overline{1}1}$

1

${X}_{\overline{1}1}$

X_{01}

Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as y_{1}y_{0}x_{1}x_{0}.

Table IV

Reduced Reference Patterns that Produce a 1 in the Last Output Digit z_{N} of the MSD Addera

0

X

1

X

1

1

X_{01}

X

X_{01}

X

1

1

X_{01}

X_{01}

1

X_{01}

X_{01}

1

1

X

1

X_{01}

X_{01}

X_{01}

1

X

X_{01}

1

Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as Y_{N−1}Y_{N−2}X_{N−1}X_{N−2}

Table V

Optimum Sets of Moduli and Number of Required Reference Patterns N_{r} for Implementing Some Practical Operations with a Content-Addressable Memory with Two-Level, Three-Level, and Five-Level Coding Alloweda

Operation

Required Range

Moduli

Corresponding Coding Levels

Covered Range

N_{r}

16-bit fixed-point addition

0–65,535

3, 5, 7, 8, 11, 13

2 or 3 or 5, 3, 2, 2, 3, 5

0–120,119

286

32-bit fixed-point addition

0–4,294,967,295

5, 7, 9, 11, 13, 16, 17, 19, 23

3, 2, 3, 3, 5, 2, 3, 3, 2

0–5,354,228,879

1001

16-bit fixed-point multiplication

0–65,535

3, 5, 7, 8, 11, 13

2 or 3 or 5, 2 or 3, 2, 2, 5, 3

0–120,119

234

32-bit fixed-point multiplication

0–4,294,967,295

5, 7, 9, 11, 13, 16, 17, 19, 23

2 or 3, 2, 3, 5, 3, 2, 3, 5, 3

0–5,354,228,879

1067

The corresponding coding level(s) shown for each modulus is (are) determined such that the number of reference patterns is minimized. For each operation, the required range of numbers and the range of numbers covered by the selected moduli are given.

Table VI

Comparison of Number of Required Reference Patterns to Perform 16-Bit Full-Precision Addition Using Various Encoding Schemes

Without Logical Reduction:

Binary

3.65 × 10^{10}

Binary–coded residue

694

Multilevel–coded residue

568

Modified–signed digit

5212

With Logical Reduction:

With Logical Reduction:

Binary

3.28 × 10^{5}

Binary–coded residue

327

Multilevel–coded residue

300

Modified–signed digit

822

Tables (6)

Table I

Truth Tables Corresponding to the Transfer (T and T^{1}) and Weight (Wand W^{1}) Functions Used In the MSD Adder

X

Y

T

W

T^{1}

W^{1}

$\overline{1}$

$\overline{1}$

$\overline{1}$

0

$\overline{1}$

0

$\overline{1}$

0

$\overline{1}$

1

0

$\overline{1}$

$\overline{1}$

1

0

0

0

0

0

$\overline{1}$

$\overline{1}$

1

0

$\overline{1}$

0

0

0

0

0

0

0

1

1

$\overline{1}$

0

1

1

$\overline{1}$

0

0

0

0

1

0

1

$\overline{1}$

0

1

1

1

1

0

1

0

Table II

Reduced Reference Patterns that Produce a 1 In the Output Digit z_{n} (n ≠ 0, 1, N) of the MSD Addera

${X}_{\overline{1}1}$

1

X

${X}_{\overline{1}1}$

1

X

0

1

X

0

1

X

${X}_{\overline{1}1}$

X_{01}

1

${X}_{\overline{1}1}$

1

X

0

X_{01}

X_{01}

0

1

X_{01}

$\overline{1}$

$\overline{1}$

X

0

1

X

0

X_{01}

1

0

1

X

${X}_{\overline{1}1}$

1

X

${X}_{\overline{1}1}$

X_{01}

1

${X}_{\overline{1}1}$

$\overline{1}$

X_{01}

0

0

1

$\overline{1}$

0

X

0

0

X

0

1

X

0

X

1

0

1

X_{01}

0

X_{01}

X_{01}

${X}_{\overline{1}1}$

$\overline{1}$

1

0

0

X_{01}

$\overline{1}$

1

X

0

$\overline{1}$

X

0

1

1

0

X_{01}

X

0

$\overline{1}$

X_{01}

${X}_{\overline{1}1}$

0

1

${X}_{\overline{1}1}$

0

X_{01}

0

$\overline{1}$

1

0

$\overline{1}$

X

$\overline{1}$

1

X

0

X_{01}

X

0

1

1

0

$\overline{1}$

1

${X}_{\overline{1}1}$

0

X_{01}

${X}_{\overline{1}1}$

0

1

0

$\overline{1}$

X_{01}

0

1

X

$\overline{1}$

$\overline{1}$

X

${X}_{\overline{1}1}$

1

1

${X}_{\overline{1}1}$

X_{01}

X

0

0

X_{01}

${X}_{\overline{1}1}$

$\overline{1}$

1

${X}_{\overline{1}1}$

X_{01}

X_{01}

${X}_{\overline{1}1}$

1

X_{01}

0

0

X

$\overline{1}$

0

X

${X}_{\overline{1}1}$

X_{01}

X

${X}_{\overline{1}1}$

1

1

0

0

1

${X}_{\overline{1}1}$

$\overline{1}$

X_{01}

${X}_{\overline{1}1}$

1

X_{01}

${X}_{\overline{1}1}$

X_{01}

X_{01}

Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as Y_{n}Y_{n−1}Y_{n−2}X_{n}X_{n−1}X_{n−2}. The digit number of the output starts with n = 0 for the least significant digit and ends with n = N for the most significant digit

Table III

Reduced Reference Patterns that Produce a 1 in the Output Digit z_{1} of the MSD Addera

0

1

$\overline{1}$

$\overline{1}$

$\overline{1}$

$\overline{1}$

0

1

0

0

$\overline{1}$

0

0

X_{01}

0

1

0

$\overline{1}$

$\overline{1}$

1

0

1

0

X_{01}

$\overline{1}$

0

0

0

${X}_{\overline{1}1}$

X_{01}

${X}_{\overline{1}1}$

1

$\overline{1}$

1

0

$\overline{1}$

${X}_{\overline{1}1}$

1

${X}_{\overline{1}1}$

X_{01}

Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as y_{1}y_{0}x_{1}x_{0}.

Table IV

Reduced Reference Patterns that Produce a 1 in the Last Output Digit z_{N} of the MSD Addera

0

X

1

X

1

1

X_{01}

X

X_{01}

X

1

1

X_{01}

X_{01}

1

X_{01}

X_{01}

1

1

X

1

X_{01}

X_{01}

X_{01}

1

X

X_{01}

1

Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as Y_{N−1}Y_{N−2}X_{N−1}X_{N−2}

Table V

Optimum Sets of Moduli and Number of Required Reference Patterns N_{r} for Implementing Some Practical Operations with a Content-Addressable Memory with Two-Level, Three-Level, and Five-Level Coding Alloweda

Operation

Required Range

Moduli

Corresponding Coding Levels

Covered Range

N_{r}

16-bit fixed-point addition

0–65,535

3, 5, 7, 8, 11, 13

2 or 3 or 5, 3, 2, 2, 3, 5

0–120,119

286

32-bit fixed-point addition

0–4,294,967,295

5, 7, 9, 11, 13, 16, 17, 19, 23

3, 2, 3, 3, 5, 2, 3, 3, 2

0–5,354,228,879

1001

16-bit fixed-point multiplication

0–65,535

3, 5, 7, 8, 11, 13

2 or 3 or 5, 2 or 3, 2, 2, 5, 3

0–120,119

234

32-bit fixed-point multiplication

0–4,294,967,295

5, 7, 9, 11, 13, 16, 17, 19, 23

2 or 3, 2, 3, 5, 3, 2, 3, 5, 3

0–5,354,228,879

1067

The corresponding coding level(s) shown for each modulus is (are) determined such that the number of reference patterns is minimized. For each operation, the required range of numbers and the range of numbers covered by the selected moduli are given.

Table VI

Comparison of Number of Required Reference Patterns to Perform 16-Bit Full-Precision Addition Using Various Encoding Schemes