%\documentclass[dvipdfmx,t,serif,mathserif,14pt]{beamer} % t: from top; serif: rmdefault
\documentclass[dvipdfmx,t,14pt]{beamer} % t: from top; serif: rmdefault
\usepackage{mybeamer}

\newcommand{\PDFTITLE}{論理回路入門（８）}
\newcommand{\PDFSUBJECT}{一年生秋学期}
\newcommand{\PDFAUTHOR}{法政大学情報科学部}
\newcommand{\PDFKEYWORDS}{
  符号なし数の掛け算、
  符号なし乗算器回路、
  符号なし CSA を使用する乗算器回路、
  符号なしウォレスツリー、
  ２の補数で表現する数の掛け算、
  ２の補数のウォレスツリーの回路}

\date{2023 年 11 月 14 日 (火)}

\title{\PDFTITLE} % bottom PDFTITLE
\subtitle{２進数の掛け算とウォレスツリー}
\author[\PDFAUTHOR]{李　亜民} % bottom PDFAUTHOR; titlepage Yamin Li

\hypersetup{
  pdftitle=\PDFTITLE,
  pdfsubject=\PDFSUBJECT,
  pdfauthor=\PDFAUTHOR,
  pdfkeywords=\PDFKEYWORDS
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\everymath={\sf}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\PDFTITLE}
\begin{frame}
  \titlepage
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%------------------------------------------------ SLIDE -
\input{mybackgroundcolor.tex}
%------------------------------------------------ SLIDE -
\section{２進数の掛け算}
\begin{frame}\frametitle{\secname}
\textcolor{blue}{ポイント}

\vspace{5mm}
\begin{itemize}
\setlength{\itemsep}{3.6mm}
\item\color{blue} 符号なし数の掛け算（乗算）
\item\color{blue} 符号なし乗算器回路
\item\color{blue} 符号なしCSAを使用する乗算器回路
\item\color{blue} 符号なしのウォレスツリー乗算器
\item\color{blue} ２の補数で表現する数の掛け算
\item\color{blue} ２の補数のウォレスツリー乗算器
\end{itemize}

\end{frame}
%------------------------------------------------ SLIDE -
\section{２進数掛け算の方式と掛け算命令}
\begin{frame}\frametitle{\secname}

\begin{enumerate}
\setlength{\itemsep}{2mm}

\item 直列掛け算
\begin{itemize}
\item 筆算と同じ、各桁を順次計算。
\end{itemize}

\item \textcolor{blue}{並列掛け算}
\begin{itemize}
\item \textcolor{blue}{組合わせ論理回路を利用、各桁を同時に計算。}
\end{itemize}

\item ROM 利用の掛け算
\begin{itemize}
\item ROM にデータを用意、演算時に読み出し。
\end{itemize}

\end{enumerate}

\color{blue}
\vspace{5mm}
CPUの掛け算命令の例（32ビット$\times$\,32ビット）
\begin{itemize}
\item \color{blue} mulh \cdotfill 64ビット積の上位 32 ビットの計算~
\item \color{blue} mul  \cdotfill 64ビット積の下位 32 ビットの計算~
\end{itemize}

\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の掛け算}
\begin{frame}\frametitle{\secname}
\fontsize{12pt}{15}\selectfont
\renewcommand{\arraystretch}{1.3}
\setlength{\tabcolsep}{6pt}
\begin{tabular}{ccccccccclr}
     &   &   &           & 1 & 1 & 1 & 0 & & \textcolor{blue}{かけられる数} & (14$_{10}$) \\[3pt]
     &   &   & $\times$  & 1 & 0 & 1 & 0 & & \textcolor{blue}{かける数}     & (10$_{10}$)\\[2pt]\cline{4-8}\ \\[-6pt]
     &   &   &           & 0 & 0 & 0 & 0 &   \multirow{4}{*}{$\left\}\begin{array}{l} \\ \\ \\ \\ \end{array}\right.$}\hspace{-6mm} \\[3pt]
     &   &   & 1         & 1 & 1 & 0 &   & & \multicolumn{2}{l}{桁に応じて}  \\[3pt]
     &   & 0 & 0         & 0 & 0 &   &   & & \multicolumn{2}{l}{ずらす} \\[3pt]
 $+$ & 1 & 1 & 1         & 0 &   &   &   & & \multicolumn{2}{l}{} \\[2pt]\cline{1-8}\ \\[-9pt]
   1 & 0 & 0 & 0         & 1 & 1 & 0 & 0 & & \textcolor{blue}{積}         & ~~(140$_{10}$) \\[-9pt]
\multicolumn{8}{c}{$\underbrace{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}$}\\[9pt]
\multicolumn{8}{c}{2倍のビット数が必要}\\
\end{tabular}
\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の掛け算}
\begin{frame}\frametitle{\secname}
\fontsize{12pt}{15}\selectfont
\renewcommand{\arraystretch}{1.3}
\setlength{\tabcolsep}{2.5pt}
\begin{tabular}{cccccccccl}
     &   &   &           & $a_3$ & $a_2$ & $a_1$ & $a_0$ & &\textcolor{blue}{かけられる数} \\[3pt]
     &   &   & $\times$  & $b_3$ & $b_2$ & $b_1$ & $b_0$ & &\textcolor{blue}{かける数}\\[2pt]\cline{4-8}\ \\[-6pt]
     &   &   &           & $a_3b_0$ & $a_2b_0$ & $a_1b_0$ & $a_0b_0$ & \hspace{-1mm}\multirow{4}{*}{$\left\}\begin{array}{l} \\ \\ \\ \\ \end{array}\right.$}\hspace{-4mm} \\[3pt]
     &   &   &         $a_3b_1$ & $a_2b_1$ & $a_1b_1$ & $a_0b_1$ &   & & $4 \times 4 = 16$ \\[3pt]
     &   &         $a_3b_2$ & $a_2b_2$ & $a_1b_2$ & $a_0b_2$ &   &   & & \textcolor{red}{AND} gates \\[3pt]
 $+$ &         $a_3b_3$ & $a_2b_3$ & $a_1b_3$ & $a_0b_3$ &   &   &   & & \\[2pt]\cline{1-8}\ \\[-11pt]
   $p_7$&$p_6$&$p_5$&$p_4$&$p_3$&$p_2$&$p_1$&$p_0$ & & \textcolor{blue}{積} \\
\end{tabular}

\vspace{4mm}
注意: $a_i \times b_i = a_i \cdot b_i = a_i  b_i$\cdotfill\color{red} AND
\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の掛け算}
\begin{frame}\frametitle{\secname}
\vspace{2mm}
\includegraphics[width=\textwidth]{figs/add8tree.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の掛け算}
\begin{frame}\frametitle{\secname}
\vspace{2mm}
\includegraphics[width=\textwidth]{figs/add8tree0.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の乗算器回路}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{12pt}{13.33}\selectfont
\begin{code}
`timescale 1ns/1ns
module and4x4 (A, B, AB0, AB1, AB2, AB3);
    input  [3:0] A, B;
    output [3:0] AB0, AB1, AB2, AB3;

    assign AB0 = A & {4{B[0]}}; // A * B[0]
    assign AB1 = A & {4{B[1]}}; // A * B[1]
    assign AB2 = A & {4{B[2]}}; // A * B[2]
    assign AB3 = A & {4{B[3]}}; // A * B[3]

endmodule




\end{code}

\vspace{-9mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/and4x4.v}{\color{blue}\underline{and4x4.v}}~~~

\vspace{-15mm}
\red 注意:

\vspace{-4mm}
\begin{verbatim}
{4{B[0]}} = {B[0],B[0],B[0],B[0]}
\end{verbatim}
\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の乗算器回路}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{12pt}{13.33}\selectfont
\begin{code}
`timescale 1ns/1ns
module mul4x4_tree (A, B, P);
    input  [3:0] A, B;
    output [7:0] P;

    wire   [3:0] AB0, AB1, AB2, AB3;
    and4x4 i0 (A, B, AB0, AB1, AB2, AB3);

    wire   [7:0] S0, S1;
    // add8 (a,                 b,                 s);
    add8 i1 ({4'b0000,AB0},     {3'b000,AB1,1'b0}, S0);
    add8 i2 ({2'b00,AB2,2'b00}, {1'b0,AB3,3'b000}, S1);
    add8 i3 (S0, S1, P);

endmodule
\end{code}

\vspace{-9mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/mul4x4_tree.v}{\color{blue}\underline{mul4x4\_tree.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の乗算器回路}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{12pt}{13.33}\selectfont
\begin{code}
`timescale 1ns/1ns
module add8 (A, B, S);
    input  [7:0] A, B;
    output [7:0] S;
    wire   [7:0] C;
    // add1 (a,    b,    ci,   co,   s);
    add1 i0 (A[0], B[0], 1'b0, C[0], S[0]);
    add1 i1 (A[1], B[1], C[0], C[1], S[1]);
    add1 i2 (A[2], B[2], C[1], C[2], S[2]);
    add1 i3 (A[3], B[3], C[2], C[3], S[3]);
    add1 i4 (A[4], B[4], C[3], C[4], S[4]);
    add1 i5 (A[5], B[5], C[4], C[5], S[5]);
    add1 i6 (A[6], B[6], C[5], C[6], S[6]);
    add1 i7 (A[7], B[7], C[6], C[7], S[7]);
endmodule
\end{code}

\vspace{-9mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/add8.v}{\color{blue}\underline{add8.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の乗算器テストベンチ}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{10pt}{10}\selectfont
\begin{code}
`timescale 1ns/1ns
module mul4x4_tree_tb;
    reg  [3:0] A, B;
    wire [7:0] P;
    mul4x4_tree i0 (A, B, P);
    integer    i, j;
    initial begin
        for (i = 0; i < 16; i = i + 1) begin
            for (j = 0; j < 16; j = j + 1) begin
                A = i; B = j;
                #1 ;
            end
        end
        #1 $finish;
    end
    initial begin
        $dumpfile ("mul4x4_tree.vcd");
        $dumpvars;
    end
endmodule
\end{code}

\vspace{-9mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/mul4x4_tree_tb.v}{\color{blue}\underline{mul4x4\_tree\_tb.v}}~~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なし数の乗算器波形}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{13pt}{14}\selectfont
\vspace{-5mm}
\begin{verbatim}
% iverilog -Wall -o mul4x4_tree mul4x4_tree_tb.v \
  mul4x4_tree.v and4x4.v add8.v add1.v half_adder.v
% ./mul4x4_tree
% gtkwave mul4x4_tree.vcd
\end{verbatim}

\includegraphics[width=\textwidth]{figs/mul4x4_tree_vcd0_crop.png}

\vspace{6mm}
\includegraphics[width=\textwidth]{figs/mul4x4_tree_vcd1_crop.png}

\vspace{6mm}
\includegraphics[width=\textwidth]{figs/mul4x4_tree_vcd2_crop.png}

\textcolor{red}{\hfill $\Uparrow$~~~}

符号なし \textcolor{blue}{$P = A \times B$}
\textcolor{red}{\hfill $15\times 15=225$}

\end{frame}
%------------------------------------------------ SLIDE -
\section{CSA を使用する乗算器回路 (4ビット)}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/mul4x4_csa.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{Wallace Tree (ウォレスツリー)}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/mul4x4_wallace.pdf}

\vspace{2mm}
\resizebox{\textwidth}{!}{\textcolor{blue}{計算可能であれば、大量のCSAを使用して並列に計算する。}}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ウォレスツリー乗算器回路}
\begin{frame}[fragile]\frametitle{\secname}
\vspace{-1mm}
\fontsize{8pt}{8}\selectfont
\begin{code}
`timescale 1ns/1ns
module wallace4 (a, b, p);
    input  [3:0] a, b;
    output [7:0] p;
    wire   [3:0] ab0, ab1, ab2, ab3;
    and4x4 i0 (a, b, ab0, ab1, ab2, ab3);
    assign p[0] = ab0[0];
    wire   [5:1] l1c; // level 1 carry
    wire   [5:2] l1s; // level 1 sum
    wire   [6:2] l2c; // level 2 carry
    wire   [6:3] l2s; // level 2 sum
    // csa  (a,      b,      ci,     co,     s); // same as add1
    csa i1  (ab1[0], ab0[1], 1'b0,   l1c[1], p[1]);   // level 1
    csa i2  (      ,       ,       ,       ,       ); // level 1
    csa i3  (      ,       ,       ,       ,       ); // level 1
    csa i4  (      ,       ,       ,       ,       ); // level 1
    csa i5  (      ,       ,       ,       ,       ); // level 1
    csa i6  (l1s[2], 1'b0,   l1c[1], l2c[2], p[2]);   // level 2
    csa i7  (      ,       ,       ,       ,       ); // level 2
    csa i8  (      ,       ,       ,       ,       ); // level 2
    csa i9  (      ,       ,       ,       ,       ); // level 2
    csa i10 (      ,       ,       ,       ,       ); // level 2
    // add5  (a,               b,        s);
    add5 i11 ({1'b0,l2s[6:3]}, l2c[6:2], p[7:3]);
endmodule
\end{code}

\vspace{-7mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/wallace4.v}{\color{blue}\underline{wallace4.v}}~~~


\vspace{-7mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/csa.v}{\color{blue}\underline{csa.v}}~~~


\end{frame}
%------------------------------------------------ SLIDE -
\section{ウォレスツリー乗算器テストベンチ}
\begin{frame}[fragile]\frametitle{\secname}
\vspace{-1mm}
\fontsize{10pt}{10}\selectfont
\begin{code}
`timescale 1ns/1ns
module wallace4_tb;
    reg  [3:0] A, B;
    wire [7:0] P;
    wallace4 i0 (A, B, P);
    integer    i, j;
    initial begin
        for (i = 0; i < 16; i = i + 1) begin
            for (j = 0; j < 16; j = j + 1) begin
                A = i; B = j;
                #1 ;
            end
        end
        #1 $finish;
    end
    initial begin
        $dumpfile ("wallace4.vcd");
        $dumpvars;
    end
endmodule
\end{code}

\vspace{-9mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/wallace4_tb.v}{\color{blue}\underline{wallace4\_tb.v}}~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{ウォレスツリー乗算器波形}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{13pt}{14}\selectfont
\vspace{-5mm}
\begin{verbatim}
% iverilog -Wall -o wallace4 wallace4_tb.v wallace4.v \
  add5.v add1.v csa.v half_adder.v and4x4.v
% ./wallace4
% gtkwave wallace4.vcd
\end{verbatim}

\includegraphics[width=\textwidth]{figs/wallace4_vcd0_crop.png}

\vspace{6mm}
\includegraphics[width=\textwidth]{figs/wallace4_vcd1_crop.png}

\vspace{6mm}
\includegraphics[width=\textwidth]{figs/wallace4_vcd2_crop.png}

\textcolor{red}{\hfill $\Uparrow$~~~}

符号なし \textcolor{blue}{$P = A \times B$}
\textcolor{red}{\hfill $15\times 15=225$}

\end{frame}
%------------------------------------------------ SLIDE -
\section{ウォレスツリー (8ビット)}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/wallace_tree_matrix_8x8.pdf}

\vspace{2.2mm}
\fontsize{13pt}{15}\selectfont

段1（L1）のCSAs（\# of CSAs：CSAの個数）

まるアスタリスク：段2（L2）に送る。

\vspace{1mm}
\textcolor{blue}{計算可能であれば、大量のCSAを使用して並列に計算する。}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ウォレスツリー (8ビット)}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/wallace_tree_8x8.pdf}

\vspace{1mm}
\fontsize{13pt}{15}\selectfont

CSA: 3 inputs $\rightarrow$ 2 outputs; \hfill \textcolor{red}{段数 $=$ log$_{3/2}n$~~}

\vspace{1.45mm}
\textcolor{blue}{計算可能であれば、大量のCSAを使用して並列に計算する。}
\end{frame}
%------------------------------------------------ SLIDE -
\section{ウォレスツリー (8ビット)}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/mul_wallace.pdf}

\vspace{-1.5mm}
\textcolor{blue}{4段CSAs}

\vspace{-74.5mm}
綺麗に整列されたウォレスツリーの回路図。

詳細については、前のページを参照してください。
\end{frame}
%------------------------------------------------ SLIDE -
\section{CSA を使用する乗算器回路 (8ビット)}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/mul_csa.pdf}

\vspace{-1.5mm}
\textcolor{blue}{7段CSAs}

\vspace{-74.5mm}
詳細については、

13ページを参照

してください。
\end{frame}
%------------------------------------------------ SLIDE -
\section{２の補数で表現する数の掛け算}
\begin{frame}\frametitle{\secname}
\fontsize{13pt}{15}\selectfont

\begin{itemize}

\item 符号なし数の掛け算

\vspace{1mm}
\textcolor{red}{
$1111 \times 1111 = 1110\underline{0001}$ \cdotfill $15 \times 15 = 225$
}

\vspace{1mm}
\textcolor{blue}{
$1111 \times 0010 = 0001\underline{1110}$ \cdotfill $15 \times \phantom{0}2 = \phantom{0}30$
}

\vspace{2mm}
\item ２の補数で表現する数の掛け算

\vspace{1mm}
\textcolor{red}{
$1111 \times 1111 = 0000\underline{0001}$ \cdotfill $\mbox{(}-1\mbox{)} \times \mbox{(}-1\mbox{)} = +1$
}

\vspace{1mm}
\textcolor{blue}{
$1111 \times 0010 = 1111\underline{1110}$ \cdotfill $\mbox{(}-1\mbox{)} \times \mbox{(}+2\mbox{)} = -2$
}

\vspace{2mm}
\item ２の補数掛け算のルール\hspace{12mm}$\uparrow$

\vspace{1mm}
正~$\times$ 正~$=$ 正\hfill\textcolor{red}{\underline{赤}：下位4ビットは同じである}

\vspace{1mm}
正~$\times$ 負~$=$ 負\hfill\textcolor{blue}{\underline{青}：下位4ビットは同じである}

\vspace{1mm}
負~$\times$ 正~$=$ 負

\vspace{1mm}
負~$\times$ 負~$=$ 正

\end{itemize}

\end{frame}
%------------------------------------------------ SLIDE -
\section{２の補数で表現する数の掛け算}
\begin{frame}\frametitle{\secname}
\includegraphics[width=.86\textwidth]{figs/signed_mul_no_good.pdf}
\end{frame}
%------------------------------------------------ SLIDE -
\section{２の補数で表現する数の掛け算}
\begin{frame}\frametitle{\secname}
\fontsize{12pt}{15}\selectfont
$\textcolor{red}{A_4}=a_3a_2a_1a_0=-a_3\times 2^3 + \sum_{i=0}^{2}a_i\times 2^i=\textcolor{red}{-a_3\times 2^3 + A_3}$

\vspace{2mm}
$\textcolor{blue}{B_4}=b_3b_2b_1b_0=-b_3\times 2^3 + \sum_{i=0}^{2}b_i\times 2^i=\textcolor{blue}{-b_3\times 2^3 + B_3}$

\vspace{2mm}
$A_3$ と~$B_3$: 符号なし数

\vspace{4mm}
$\mbox{(}a+b\mbox{)}\mbox{(}x+y\mbox{)}=ax + ay + bx + by$ なので、

\vspace{2mm}
\renewcommand{\arraystretch}{1.2}
\tabcolsep = 4pt
\begin{tabular}{rcl}
\hspace*{-2.5mm}
$P_8$ & $=$ & $\textcolor{red}{A_4} \times \textcolor{blue}{B_4}$\\
      & $=$ & $\textcolor{red}{\mbox{(}-a_3\times 2^3 + A_3\mbox{)}} \times \textcolor{blue}{\mbox{(}-b_3\times 2^3 + B_3\mbox{)}}$\\
      & $=$ & $a_3 \times b_3  \times 2^6$\\
      & $+$ & $\mbox{(}-a_3 \times B_3\mbox{)} \times 2^3$ \ \ \textcolor{magenta}{(負)}\\
      & $+$ & $\mbox{(}-b_3 \times A_3\mbox{)} \times 2^3$ \ \ \textcolor{magenta}{(負)}\\
      & $+$ & $A_3 \times B_3$\\
\end{tabular}
\end{frame}
%------------------------------------------------ SLIDE -
\section{２の補数で表現する数の掛け算}
\begin{frame}\frametitle{\secname}
\fontsize{13pt}{15}\selectfont
$-X = \overline{X} + 1$ なので、

\vspace{4mm}
$\mbox{(}-a_3 \times B_3\mbox{)} \times \textcolor{red}{2^3} = \mbox{(}\overline{0},\overline{0},\overline{a_3b_2},\overline{a_3b_1},\overline{a_3b_0}+1\mbox{)}\times \textcolor{red}{2^3}$

\vspace{2.65mm}
$\mbox{(}-b_3 \times A_3\mbox{)} \times \textcolor{red}{2^3} = \mbox{(}\overline{0},\overline{0},\overline{a_2b_3},\overline{a_1b_3},\overline{a_0b_3}+1\mbox{)}\times \textcolor{red}{2^3}$

\vspace{7.5mm}
つまり

\vspace{5mm}
{\renewcommand{\arraystretch}{1.3}
\tabcolsep = 9pt
\begin{tabular}{rcccccc}
\textcolor{red}{Bit\#} & ~~7~~   &  ~~6~~  &           5         &           4         &         \textcolor{red}{3}          \\\cline{1-6}
      & \blue \rule{0pt}{\normalbaselineskip}1 & \blue 1 & $\overline{a_3b_2}$ & $\overline{a_3b_1}$ & $\overline{a_3b_0}$&\blue 反転\\[-2pt]
      & \blue 0 & \blue 0 &     \blue 0         &     \blue 0         &   \blue 1          &\blue $+1$\\[-2pt]
      & \blue 1 & \blue 1 & $\overline{a_2b_3}$ & $\overline{a_1b_3}$ & $\overline{a_0b_3}$&\blue 反転\\[-2pt]
  $+$ & \blue 0 & \blue 0 &    \blue  0         &     \blue 0         &   \blue 1          &\blue $+1$\\\cline{1-6}
\end{tabular}
}

\end{frame}
%------------------------------------------------ SLIDE -
\section{２の補数で表現する数の掛け算}
\begin{frame}\frametitle{\secname}
\fontsize{13pt}{15}\selectfont
{\renewcommand{\arraystretch}{1.3}
\tabcolsep = 9pt
\begin{tabular}{rcccccc}
\textcolor{red}{Bit\#} & ~~7~~   &  ~~6~~  &           5         &           4         &         \textcolor{red}{3}          \\\cline{1-6}
      & \blue \rule{0pt}{\normalbaselineskip}1 & \blue 1 & $\overline{a_3b_2}$ & $\overline{a_3b_1}$ & $\overline{a_3b_0}$&\blue 反転\\[-2pt]
      & \blue 0 & \blue 0 &     \blue 0         &     \blue 0         &   \blue 1          &\blue $+1$\\[-2pt]
      & \blue 1 & \blue 1 & $\overline{a_2b_3}$ & $\overline{a_1b_3}$ & $\overline{a_0b_3}$&\blue 反転\\[-2pt]
  $+$ & \blue 0 & \blue 0 &    \blue  0         &     \blue 0         &   \blue 1          &\blue $+1$\\\cline{1-6}
\end{tabular}
}

\vspace{6mm}
整理

\vspace{3.38mm}

{\renewcommand{\arraystretch}{1.3}
\tabcolsep = 9pt
\begin{tabular}{rccccc}
\textcolor{red}{Bit\#} & ~~\textcolor{red}{7}~~   &  ~~6~~  &           5         &           \textcolor{red}{4}         &         3          \\\hline
      & \rule{0pt}{\normalbaselineskip}$0$ & $0$ & $\color{red}\overline{a_3b_2}$ & $\color{red}\overline{a_3b_1}$ & $\color{red}\overline{a_3b_0}$\\[-2pt]
      & $0$ & $0$ & $\color{red}\overline{a_2b_3}$ & $\color{red}\overline{a_1b_3}$ & $\color{red}\overline{a_0b_3}$\\[-2pt]
  $+$ & \color{red} 1  &  0  &           0         &          \color{red} 1         &         0          \\\hline
\end{tabular}
}
\end{frame}
%------------------------------------------------ SLIDE -
\section{２の補数のウォレスツリーの回路}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/mul4x4_wallace_signed.pdf}

\end{frame}
%------------------------------------------------ SLIDE -
\section{テストベンチ}
\begin{frame}[fragile]\frametitle{\secname}
\vspace{-1mm}
\fontsize{10pt}{10}\selectfont
\begin{code}
`timescale 1ns/1ns
module wallace4_signed_tb;
    reg  [3:0] A, B;
    wire [7:0] P;
    wallace4_signed i0 (A, B, P);
    integer    i, j;
    initial begin
        for (i = 0; i < 16; i = i + 1) begin
            for (j = 0; j < 16; j = j + 1) begin
                A = i; B = j;
                #1 ;
            end
        end
        #1 $finish;
    end
    initial begin
        $dumpfile ("wallace4_signed.vcd");
        $dumpvars;
    end
endmodule
\end{code}

\vspace{-9mm}
\hfill
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/wallace4_signed_tb.v}{\color{blue}\underline{wallace4\_signed\_tb.v}}~~

\end{frame}
%------------------------------------------------ SLIDE -
\section{２の補数のウォレスツリーの波形}
\begin{frame}[fragile]\frametitle{\secname}
\fontsize{10pt}{14}\selectfont
\vspace{-5mm}
\begin{verbatim}
% iverilog -Wall -o wallace4_signed wallace4_signed_tb.v \
  wallace4_signed.v add5.v add1.v csa.v half_adder.v and4x4.v
% ./wallace4_signed
% gtkwave wallace4_signed.vcd
\end{verbatim}

\fontsize{13pt}{14}\selectfont
\includegraphics[width=\textwidth]{figs/wallace4_signed_vcd0_crop.png}

\vspace{6mm}
\includegraphics[width=\textwidth]{figs/wallace4_signed_vcd1_crop.png}

\vspace{6mm}
\includegraphics[width=\textwidth]{figs/wallace4_signed_vcd2_crop.png}

\textcolor{red}{\hfill $\Uparrow$~~~}

２の補数 \textcolor{blue}{$P = A \times B$}
\textcolor{red}{\hfill $(-1)\times (-1)=1$}

\end{frame}
%------------------------------------------------ SLIDE -
\section{符号なしのウォレスツリーの回路}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/mul4x4_wallace_unsigned.pdf}

\end{frame}
%------------------------------------------------ SLIDE -
\section{２の補数のウォレスツリーの回路}
\begin{frame}\frametitle{\secname}
\includegraphics[width=\textwidth]{figs/mul4x4_wallace_signed.pdf}

\end{frame}
%------------------------------------------------ SLIDE -
\section{２進数の掛け算}
\begin{frame}\frametitle{\secname}
\textcolor{blue}{まとめ}

\vspace{5mm}
\begin{itemize}
\setlength{\itemsep}{3.6mm}
\item\color{blue} 符号なし数の掛け算（乗算）
\item\color{blue} 符号なし乗算器回路
\item\color{blue} 符号なしCSAを使用する乗算器回路
\item\color{blue} 符号なしのウォレスツリー乗算器
\item\color{blue} ２の補数で表現する数の掛け算
\item\color{blue} ２の補数のウォレスツリー乗算器
\end{itemize}

\end{frame}
%------------------------------------------------ SLIDE -
\section{課題~VIII (100 点~+ 200 点)}
\begin{frame}\frametitle{\secname}
\fontsize{12pt}{14}\selectfont
４ビット$\times$４ビット\textcolor{red}{符号なし}のウォレスツリーを設計し動作検証\\シミュレーションして下さい。

\vspace{3mm}
入力信号: A[3:0] \cdotfill 4-bit data~

入力信号: B[3:0] \cdotfill 4-bit data~

出力信号: P[7:0] \cdotfill 8-bit result~

\vspace{3mm}
モジュール名は~\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/wallace4.v}{\textcolor{blue}{\underline{wallace4}}} にすること。\\
\mbox{テストベンチ~\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/wallace4_tb.v}{\textcolor{blue}{\underline{wallace4\_tb.v}}} を使って下さい。}

\vspace{5mm}
\textcolor{brown}{オプション~($+50$ 点):}
４ビット$\times$４ビット\textcolor{red}{２の補数}のウォレスツリーを設計し動作検証シミュレーションして下さい。

モジュール名は~\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/wallace4_signed.v}{\textcolor{blue}{\underline{wallace4\_signed}}} にすること。

テストベンチ
\href{https://yamin.cis.k.hosei.ac.jp/lectures/logic/wallace4_signed_tb.v}{\textcolor{blue}{\underline{wallace4\_signed\_tb.v}}} を使って下さい。
\end{frame}
%------------------------------------------------ SLIDE -
\section{課題~VIII (100 点~+ 200 点)}
\begin{frame}\frametitle{\secname}
\fontsize{12pt}{14}\selectfont
\textcolor{brown}{オプション~($+100$ 点):}８ビット$\times$８ビット\textcolor{red}{符号なし}のウォレスツリーを設計し動作検証シミュレーションして下さい。

\vspace{3mm}
入力信号: A[7:0] \cdotfill 8-bit data~

入力信号: B[7:0] \cdotfill 8-bit data~

出力信号: P[15:0] \cdotfill 16-bit result~

\vspace{3mm}
モジュール名は~wallace8 にすること。\phantom{$\underline{4l}$}\\
テストベンチを自分で作って下さい。\phantom{$\underline{4l}$}

\vspace{5mm}
\textcolor{brown}{オプション~($+50$ 点):}
８ビット$\times$８ビット\textcolor{red}{２の補数}のウォレスツリーを設計し動作検証シミュレーションして下さい。

モジュール名は~wallace8\_signed にすること。\phantom{$\underline{gd}$}

テストベンチを自分で作って下さい。\phantom{$\underline{gd}$}
\end{frame}
%------------------------------------------------ SLIDE -
\input{mybackground.tex}
%------------------------------------------------ SLIDE -
\section{発展：自由練習}
\begin{frame}\frametitle{\secname}
P13のCSAを使用する4ビット乗算器回路を設計し動作検証シミュレーションして下さい。
\end{frame}
%------------------------------------------------ SLIDE -
\section{発展：自由練習}
\begin{frame}\frametitle{\secname}
\fontsize{12pt}{14}\selectfont

Sを\textcolor{red}{符号なし}の４ビットAかける４ビットBの８ビット積とする

$$\mathsf{A_3A_2A_1A_0 \times B_3B_2B_1B_0 = S_7S_6S_5S_4S_3S_2S_1S_0}$$

\vspace{9mm}
Tを\textcolor{red}{２の補数}の４ビットAかける４ビットBの８ビット積とする

$$\mathsf{A_3A_2A_1A_0 \times B_3B_2B_1B_0 = T_7T_6T_5T_4T_3T_2T_1T_0}$$

\vspace{9mm}
証明：

$$\mathsf{S_3S_2S_1S_0 = T_3T_2T_1T_0}$$
\end{frame}
%------------------------------------------------ SLIDE -
\end{document}
%------------------------------------------------ SLIDE -
