%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% copyright (C) 1998 Keiichi Ishioka				       %
% 								       %
% �������ɽ�������ܤ��Ƥ���ʤ��, �ɤΤ褦�����ΤˤǤⲿ����ä� %
% ����ʣ�̤��ƺ����դ��뤳�Ȥ���Ĥ��ޤ�. �����Υɥ�����ȤȤ��λ� % 
% �ѵ�����¾�θ������������ݤ�, �ʲ��ξ��˽��äƲ�����.	       %
% 								       %
% ¾�θ������������ݤ�, ¾�θ���Ǥθ���ɽ���ؤ��ѹ����ϰϤ�ۤ��Ƹ� %
% �դ˰�̣���ѹ����ʤ�����.					       %
%								       %
% �����������ѵ����ˤ�, ���줬�����Ǥ��뤳��, �ޤ���ʸ�λ��ѵ��������� %
% ���Τ˰���Ŭ�Ѥ���뤳�Ȥ��������뤳��.			       %
%								       %
% �ϥ��ѡ��ƥ����Ȥξ��, Ʊ�쥵���Ⱦ�Ǹ�ʸ�Υ��ԡ����ݼ餹�뤳��. �� %
% ��, ���������ϥ��ѡ��ƥ����ȤΥڡ������餽�θ�ʸ�ؤΥ�󥯤��󶡤��� %
% ����.								       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%����   95/08/30 �в����� (version 0.0)
%���� 2000/09/19 �в����� (version 1.0)
%
\documentclass[a4j]{jarticle}

\newcommand{\R}{\mbox{Re}}
\newcommand{\I}{\mbox{Im}}
\newcommand{\ttM}{{\tt M}}
\newcommand{\ttN}{{\tt N}}

\title{FTPACK���Ѥμ�� (version 1.0)}
\author{�в� ����  (2000/09/19)}
\date{}

\begin{document}

\maketitle

\section{����}

�����, ��®�ա��ꥨ�Ѵ���Ԥʤ����֥롼����ѥå������Ǥ���.
�ǡ�������������Ǥ������Ϣ³Ū�ˤ��뤳�Ȥˤ��,
�٥��ȥ�׻�����Ǥι�®����Ϥ��äƤ��뤬, �̾�η׻�����ǻ��Ѥ���
�⽽ʬ��®�Ǥ���(������, �̾�η׻�����CPU����ӥ���å����������
��ʬ��θ���ƺ�Ŭ�����줿FFT�롼����, �㤨��FFTW
({\tt http://www.fftw.org/})�ˤϤ������ˤ��ʤ�ʤ��Τ�, ���Τ褦�ʷ׻���
��FFT��¹Ԥ���ɬ�פ�����, ���ļ¹Ի��֤κ︺�����פǤ�����ˤ�, ����
�褦�ʺ�Ŭ�����줿FFT�롼����λ��Ѥ������).
�ʤ�, �Ѵ��δ����2,3,4,5�Ǥ���Τ�, �������ǰ������Ѥ�ɽ�����ǡ���
Ĺ���Ѵ��˸¤���.

\vspace{1em}
�ʲ��Υ��֥롼���󷲤���ǽ�����򤪤��ʤ����֥롼����
(���֥롼����̾��{\tt I}�ǽ����)��, ���Υ��֥롼���󷲤�°����
�Ѵ��롼������Ѥ����, ���ʤ餺�ǽ��1��ƤФʤ���Фʤ�ʤ�. 
����������ʸ��, �ۤʤ�ǡ���������ꤹ��Ȥ��˸¤ä�
������롼�����Ƥ٤Ф褤. 
�ʤ�, ������롼�����Ѥ������ΰ��, Ʊ�����֥롼���󷲤�
°�����Ѵ��롼������Ѥ��Ƥ�����ѹ����ƤϤʤ�ʤ�. 
(���κ���ΰ�ˤ�, �����Ȼ��Ѵؿ�ɽ����Ǽ����Ƥ���). 

\vspace{1em}
�ޤ�, �٥��ȥ벽�θ�Ψ��夲�뤿���, Ʊ������λ�����ǡ�����ʣ����Ʊ
���˥ա��ꥨ�Ѵ�������ͤˤʤäƤ���. �Ĥޤ�, 2��������
{\tt X(I,J),I=1,2,$\cdots$,M, J=1,2,$\cdots$,N}��Ϳ����줿���, 
��{\tt I}�ˤĤ���, {\tt X(I,1),X(I,2),$\cdots$,X(I,N)}���Ф���ա��ꥨ
�Ѵ���Ԥʤ�. ���ʤ��, ���ξ��{\tt N}��Υա��ꥨ�Ѵ���{\tt M}
�󷫤��֤����Ȥˤʤ�. ������ǡ�����1��������ξ���{\tt M=1}�Ȥ���
�Ф褤.

\newpage  
\section{���֥롼����Υꥹ��}

  Υ��������ʣ�ǥա��ꥨ�Ѵ�

  \vspace{1em}
  \begin{tabular}{p{7cm}p{10cm}}
    {\tt FTTZLI(N,IT,T)} & ������򤪤��ʤ�.\\
    {\tt FTTZLM(M,N,X,Y,IT,T)} & �Ѵ��򤪤��ʤ�.
  \end{tabular}

  Υ����ʣ�ǥա��ꥨ�Ѵ�

  \vspace{1em}
  \begin{tabular}{p{7cm}p{10cm}}
    {\tt FTTZUI(N,IT,T)} & ������򤪤��ʤ�.\\
    {\tt FTTZUF(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�.\\
    {\tt FTTZUB(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�.
  \end{tabular}

 \vspace{1em}
  Υ�����¥ա��ꥨ�Ѵ�

  \vspace{1em}
  \begin{tabular}{p{7cm}p{10cm}}
    {\tt FTTRUI(N,IT,T)} & ������򤪤��ʤ�.\\
    {\tt FTTRUF(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�.\\
    {\tt FTTRUB(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�.
  \end{tabular}
  
 \vspace{1em}
  Υ����cosine�Ѵ�(�������)

  \vspace{1em}
  \begin{tabular}{p{7cm}p{10cm}}
    {\tt FTTCTI(N,IT,T)} & ������򤪤��ʤ�. \\
    {\tt FTTCTF(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�. \\
    {\tt FTTCTB(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�.
  \end{tabular}

 \vspace{1em}
  Υ����sine�Ѵ�(�������)

  \vspace{1em}
  \begin{tabular}{p{7cm}p{10cm}}
    {\tt FTTSTI(N,IT,T)} & ������򤪤��ʤ�. \\
    {\tt FTTSTF(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�. \\
    {\tt FTTSTB(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�.
  \end{tabular}

 \vspace{1em}
  Υ����cosine�Ѵ�(��������)

  \vspace{1em}
  \begin{tabular}{p{7cm}p{10cm}}
    {\tt FTTCMI(N,IT,T)} & ������򤪤��ʤ�. \\
    {\tt FTTCMF(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�. \\
    {\tt FTTCMB(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�.
  \end{tabular}

 \vspace{1em}
  Υ����sine�Ѵ�(��������)

  \vspace{1em}
  \begin{tabular}{p{7cm}p{10cm}}
    {\tt FTTSMI(N,IT,T)} & ������򤪤��ʤ�. \\
    {\tt FTTSMF(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�. \\
    {\tt FTTSMB(M,N,X,Y,IT,T)} & ���Ѵ��򤪤��ʤ�.
  \end{tabular}
  
\newpage  
\section{���֥롼���������}

\subsection{FTTZLI/FTTZLM}
\begin{enumerate}
  \item ��ǽ 
  \begin{quote}
    1����(���$N$)��ʣ�ǻ�����ǡ���$\{\alpha_k\}$��$M$��Ϳ����줿�Ȥ�, 
    Υ��������ʣ�ǥա��ꥨ�Ѵ���FFT�ˤ��Ԥʤ�. ������, 
    $N$��$N=2^a3^b5^c(a,b,c: 0�ޤ��ϼ�����)$�Ǥ��뤳��. 
     {\tt FTTZLI}�Ͻ������Ԥ�;
     {\tt FTTZLM}�ϥա��ꥨ�Ѵ���Ԥ�.

  \end{quote}
  \item ���
    \begin{itemize}
     \item ����ʣ�ǥա��ꥨ�Ѵ�
      \begin{quote}
       $\{\alpha_k\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{x_j\}$�����. 
       $$x_j=\sum^{N-1}_{k=0}\alpha_k\exp(2\pi i\frac{jk}N),
       \quad j=0,1,\cdots,N-1$$
      \end{quote}
     \end{itemize}    
  \item �ƤӽФ���ˡ 
  \begin{quote}
    {\tt FTTZLI(N,IT,T)}\\
    {\tt FTTZLM(M,N,X,Y,IT,T)}
  \end{quote}
  \item �ѥ�᡼���������� 
  \begin{quote}
    \begin{tabular}{llp{10cm}}
      {\tt M }   & {\tt (I)} & ����. Ʊ�����Ѵ����������θĿ�$M$\\
      {\tt N }   & {\tt (I)} & ����. �Ѵ��ι��$N$\\
      {\tt X }   & {\tt (D)} & ����. $\{\alpha_k\}$\\
                 &           & ����. $\{x_j\}$\\
                 &           & �礭��\ttM$\times$\ttN$\times$2��3��������\\
      {\tt Y }   & {\tt (D)} & ����ΰ�. �礭��\ttM$\times$\ttN$\times$2
                               ��1��������\\
      {\tt IT}   & {\tt (I)} & ����ΰ�. �礭��5��1��������\\
      {\tt T }   & {\tt (D)} & ����ΰ�. �礭��\ttN$\times$2��1��������
    \end{tabular}
  \end{quote}

  \item �ǡ����γ�Ǽ��ˡ

  \begin{quote}

  {\tt X(M,0:N-1,2)}���������Ƥ�����, ��I�ˤĤ��ưʲ��Τ�
   ���˥ǡ�������Ǽ�����.

    \begin{tabular}{|c|c|c|c|c|c|c|}\hline
     \tt X(I,0,1) & \tt X(I,0,2) & \tt X(I,1,1) & \tt X(I,1,2) & 
     $\cdots$ & \tt X(I,N-1,1) & \tt X(I,N-1,2) \\\hline\hline
      \R($x_0$) & \I($x_0$) & \R($x_1$) & \I($x_1$) &
     $\cdots$ & \R($x_{N-1}$) & \I($x_{N-1}$) \\\hline
      \R($\alpha_0$) & \I($\alpha_0$) & \R($\alpha_1$) & \I($\alpha_1$) &
     $\cdots$ & \R($\alpha_{N-1}$) & \I($\alpha_{N-1}$) \\\hline
    \end{tabular}
  \end{quote}

\end{enumerate}

\newpage  
\subsection{FTTZUI/FTTZUF/FTTZUB}
\begin{enumerate}
  \item ��ǽ 
  \begin{quote}
    1����(���$N$)��ʣ�ǻ�����ǡ���$\{x_j\}$�ޤ���$\{\alpha_k\}$��$M$
    ��Ϳ����줿�Ȥ�, 
    Υ����ʣ�ǥա��ꥨ���Ѵ�, �ޤ��Ϥ��ε��Ѵ���FFT�ˤ��Ԥ�. ������, 
    $N$��$N=2^a3^b5^c(a,b,c: 0�ޤ��ϼ�����)$�Ǥ��뤳��. 
     {\tt FTTZUI}�Ͻ������Ԥ�;
     {\tt FTTZUF}�ϥա��ꥨ���Ѵ���Ԥ�;
     {\tt FTTZUB}�ϥա��ꥨ���Ѵ���Ԥ�.

  \end{quote}
  \item ���
    \begin{itemize}
     \item �ա��ꥨ���Ѵ�
      \begin{quote}
       $\{x_j\}$�����Ϥ��������Ѵ���Ԥʤ���$\{\alpha_k\}$�����.
       $$\alpha_k=\frac1N\sum^{N-1}_{j=0}x_j\exp(-2\pi i\frac{jk}N),
       \quad k=0,1,\cdots,N-1$$
      \end{quote}
     \item �ա��ꥨ���Ѵ�
      \begin{quote}
       $\{\alpha_k\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{x_j\}$�����.
       $$x_j=\sum^{N-1}_{k=0}\alpha_k\exp(2\pi i\frac{jk}N),
       \quad j=0,1,\cdots,N-1$$
      \end{quote}
     \end{itemize}    
  \item �ƤӽФ���ˡ 
  \begin{quote}
    {\tt FTTZUI(N,IT,T)}\\
    {\tt FTTZUF(M,N,X,Y,IT,T)}\\
    {\tt FTTZUB(M,N,X,Y,IT,T)}
  \end{quote}
  \item �ѥ�᡼���������� 
  \begin{quote}
    \begin{tabular}{llp{10cm}}
      {\tt M }   & {\tt (I)} & ����. Ʊ�����Ѵ����������θĿ�$M$\\
      {\tt N }   & {\tt (I)} & ����. �Ѵ��ι��$N$\\
      {\tt X }   & {\tt (D)} & ����. $\{x_j\}$�ޤ���$\{\alpha_k\}$\\
                 &           & ����. $\{\alpha_k\}$�ޤ���$\{x_j\}$\\
                 &           & �礭��\ttM$\times$\ttN$\times$2��3��������\\
      {\tt Y }   & {\tt (D)} & ����ΰ�. �礭��\ttM$\times$\ttN$\times$2
                               ��1��������\\
      {\tt IT}   & {\tt (I)} & ����ΰ�. �礭��5��1��������\\
      {\tt T }   & {\tt (D)} & ����ΰ�. �礭��\ttN$\times$2��1��������
    \end{tabular}
  \end{quote}

  \item �ǡ����γ�Ǽ��ˡ

  \begin{quote}

  {\tt X(M,0:N-1,2)}���������Ƥ�����, ��I�ˤĤ��ưʲ��Τ�
   ���˥ǡ�������Ǽ�����.

    \begin{tabular}{|c|c|c|c|c|c|c|}\hline
     \tt X(I,0,1) & \tt X(I,0,2) & \tt X(I,1,1) & \tt X(I,1,2) & 
     $\cdots$ & \tt X(I,N-1,1) & \tt X(I,N-1,2) \\\hline\hline
      \R($x_0$) & \I($x_0$) & \R($x_1$) & \I($x_1$) &
     $\cdots$ & \R($x_{N-1}$) & \I($x_{N-1}$) \\\hline
      \R($\alpha_0$) & \I($\alpha_0$) & \R($\alpha_1$) & \I($\alpha_1$) &
     $\cdots$ & \R($\alpha_{N-1}$) & \I($\alpha_{N-1}$) \\\hline
    \end{tabular}
  \end{quote}

\end{enumerate}

\newpage  
\subsection{FTTRUI/FTTRUF/FTTRUB}
\begin{enumerate}
  \item ��ǽ 
  \begin{quote}
    1����(���$N$)�μ»�����ǡ���$\{x_j\}$��$M$��Ϳ����줿�Ȥ�,
    Υ�����¥ա��ꥨ���Ѵ�, �ޤ��Ϥ��ε��Ѵ���FFT�ˤ��Ԥ�. ������, 
    $N$�϶�����, ����$N/2=2^a3^b5^c(a,b,c: 0�ޤ��ϼ�����)$�Ǥ��뤳��.
     {\tt FTTRUI}�Ͻ������Ԥ�;
     {\tt FTTRUF}�ϥա��ꥨ���Ѵ���Ԥ�;
     {\tt FTTRUB}�ϥա��ꥨ���Ѵ���Ԥ�.

  \end{quote}
  \item ���
    \begin{itemize}
     \item �ա��ꥨ���Ѵ�
      \begin{quote}
       $\{x_j\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{a_k\},\{b_k\}$�����. 
       $$a_k= \frac1N\sum^{N-1}_{j=0}x_j\cos\frac{2\pi jk}N,
       \quad k=0,1,\cdots,N/2$$
       $$b_k=-\frac1N\sum^{N-1}_{j=0}x_j\sin\frac{2\pi jk}N,
       \quad k=1,2,\cdots,N/2-1$$
      \end{quote}
     \item �ա��ꥨ���Ѵ�
      \begin{quote}
       $\{a_k\},\{b_k\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{x_j\}$�����. 
       $$x_j=a_0+a_{N/2}(-1)^j+2\sum^{N/2-1}_{k=1}(a_k\cos\frac{2\pi jk}N
                          -b_k\sin\frac{2\pi jk}N)
       \quad j=0,1,\cdots,N-1$$
      \end{quote}
     \end{itemize}    
  \item �ƤӽФ���ˡ 
  \begin{quote}
    {\tt FTTRUI(N,IT,T)}\\
    {\tt FTTRUF(M,N,X,Y,IT,T)}\\
    {\tt FTTRUB(M,N,X,Y,IT,T)}
  \end{quote}
  \item �ѥ�᡼���������� 
  \begin{quote}
    \begin{tabular}{llp{10cm}}
      {\tt M }&{\tt (I)}& ����. Ʊ�����Ѵ����������θĿ�$M$\\
      {\tt N }&{\tt (I)}& ����. �Ѵ��ι��$N$\\
      {\tt X }   & {\tt (D)} & ����. $\{x_j\}$�ޤ���$\{a_k\},\{b_k\}$\\
                 &           & ����. $\{a_k\},\{b_k\}$�ޤ���$\{x_j\}$\\
                 &           & �礭��\ttM$\times$\ttN ��2��������\\
      {\tt Y }   & {\tt (D)} & ����ΰ�. �礭��\ttM$\times$\ttN ��1��������\\
      {\tt IT}   & {\tt (I)} & ����ΰ�. �礭��5��1��������\\
      {\tt T }   & {\tt (D)} & ����ΰ�. �礭��\ttN$\times$2��1��������
    \end{tabular}
  \end{quote}

  \item �ǡ����γ�Ǽ��ˡ
  \begin{quote}

  {\tt X(M,0:N-1)}���������Ƥ�����, ��I�ˤĤ��ưʲ��Τ�
   ���˥ǡ�������Ǽ�����.

    \begin{tabular}{|c|c|c|c|c|c|c|}\hline
     \tt X(I,0) & \tt X(I,1) & \tt X(I,2) & \tt X(I,3) & 
     $\cdots$ & \tt X(I,N-2) & \tt X(I,N-1) \\\hline\hline
      $x_0$ & $x_1$ & $x_2$ & $x_3$ &
     $\cdots$ & $x_{N-2}$ & $x_{N-1}$ \\\hline
      $a_0$ & $a_{N/2}$ & $a_1$ & $b_1$ &
     $\cdots$ & $a_{N/2-1}$ & $b_{N/2-1}$ \\\hline
    \end{tabular}

  \end{quote}

\end{enumerate}

\subsection{FTTCTI/FTTCTF/FTTCTB}

\begin{enumerate}

  \item ��ǽ 
  \begin{quote}
    ����$2\pi$�ζ��ؿ�$x(t)$��Ⱦ������$N$��ʬ����$N+1$�Ĥ�ɸ��
    $\{x_j\}$,
     $$x_j=x(\frac{\pi j}{N}), \quad j=0,1,\cdots,N $$
    ��$M$��Ϳ����줿�Ȥ�, ��������ˤ��
    Υ����cosine�Ѵ�, �ޤ��Ϥ��ε��Ѵ���FFT�ˤ��Ԥʤ�. ������, 
    $N$�϶�����, ����$N/2=2^a3^b5^c(a,b,c: 0�ޤ��ϼ�����)$�Ǥ��뤳��.
  \end{quote}

  \item ���
    \begin{itemize}
     \item cosine���Ѵ�(�������)
      \begin{quote}
       $\{x_j\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{a_k\}$�����.
       $$a_k= \frac2N\left(\frac12 x_0+\frac12 x_N(-1)^k
              +\sum^{N-1}_{j=1}x_j\cos\frac{\pi jk}N\right)
       \quad (k=0,1,\cdots,N)$$
      \end{quote}

     \item cosine���Ѵ�(�������)(���Ѵ�������ܰۤʤ����)
      \begin{quote}
       $\{a_k\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{x_j\}$�����.
       $$x_j=\frac12 a_0+\frac12 a_N(-1)^j
              +\sum^{N-1}_{k=1}a_k\cos\frac{\pi jk}N
       \quad (j=0,1,\cdots,N)$$
      \end{quote}
     \end{itemize}    

  \item �ƤӽФ���ˡ 
  \begin{quote}
    {\tt FTTCTI(N,IT,T)}\\
    {\tt FTTCTF(M,N,X,Y,IT,T)}\\
    {\tt FTTCTB(M,N,X,Y,IT,T)}
  \end{quote}
  \item �ѥ�᡼���������� 
  \begin{quote}
    \begin{tabular}{llp{10cm}}
      {\tt M }&{\tt (I)}& ����. Ʊ�����Ѵ����������θĿ�\\
      {\tt N }&{\tt (I)}& ����. �Ѵ��ι�� - 1 ($N$)\\
      {\tt X }   & {\tt (D)} & ����. $\{x_j\}$�ޤ���$\{a_k\}$\\
                 &           & ����. $\{a_k\}$�ޤ���$\{x_j\}$\\
                 &           & �礭��\ttM$\times${\tt (N+1)}��2��������\\
      {\tt Y }   & {\tt (D)} & ����ΰ�. �礭��\ttM$\times$\ttN ��1��������\\
      {\tt IT}   & {\tt (I)} & ����ΰ�. �礭��5��1��������\\
      {\tt T }   & {\tt (D)} & ����ΰ�. �礭��3\ttN ��1��������
    \end{tabular}
  \end{quote}

  \item �ǡ����γ�Ǽ��ˡ
  \begin{quote}
  
  {\tt X(M,0:N)}���������Ƥ�����, ��I�ˤĤ��ưʲ��Τ�
   ���˥ǡ�������Ǽ�����.

    \begin{tabular}{|c|c|c|c|c|}\hline
     \tt X(I,0) & \tt X(I,1) & 
     $\cdots$ & \tt X(I,N-1) & \tt X(I,N) \\\hline\hline
      $x_0$ & $x_1$ & 
     $\cdots$ & $x_{N-1}$ & $x_{N}$ \\\hline
      $a_0$ & $a_1$ & 
     $\cdots$ & $a_{N-1}$ & $a_{N}$ \\\hline
    \end{tabular}
  \end{quote}
  
  \item ����
 
   \begin{itemize}
    \item ����{\tt X}��{\tt Y}�Ȥ��礭�����ۤʤ뤳�Ȥ�����.
    \end{itemize}

\end{enumerate}

\subsection{FTTSTI/FTTSTF/FTTSTB}

\begin{enumerate}

  \item ��ǽ 
  \begin{quote}
    ����$2\pi$�δ�ؿ�$x(t)$��Ⱦ������$N$��ʬ����$N-1$�Ĥ�ɸ��
    $\{x_j\}$,
     $$x_j=x(\frac{\pi j}{N}), \quad j=1,2,\cdots,N-1 $$
    ��$M$��Ϳ����줿�Ȥ�, ��������ˤ��
    Υ����sine�Ѵ�, �ޤ��Ϥ��ε��Ѵ���FFT�ˤ��Ԥʤ�. ������, 
    $N$�϶�����, ����$N/2=2^a3^b5^c(a,b,c: 0�ޤ��ϼ�����)$�Ǥ��뤳��.
  \end{quote}

  \item ���
    \begin{itemize}
     \item sine�Ѵ�(�������)
      \begin{quote}
       $\{x_j\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{b_k\}$�����.
       $$b_k= \frac2N\sum^{N-1}_{j=1}x_j\sin\frac{\pi jk}{N}
       \quad (k=1,2,\cdots,N-1)$$
      \end{quote}

     \item sine���Ѵ�(�������)(���Ѵ�������ܰۤʤ����)
      \begin{quote}
       $\{b_k\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{x_j\}$�����.
       $$x_j=\sum^{N-1}_{k=1}b_k\sin\frac{\pi jk}{N}
       \quad (j=1,2,\cdots,N-1)$$
      \end{quote}
     \end{itemize}    

  \item �ƤӽФ���ˡ 
  \begin{quote}
    {\tt FTTSTI(N,IT,T)}\\
    {\tt FTTSTF(M,N,X,Y,IT,T)}\\
    {\tt FTTSTB(M,N,X,Y,IT,T)}
  \end{quote}
  \item �ѥ�᡼���������� 
  \begin{quote}
    \begin{tabular}{llp{10cm}}
      {\tt M }&{\tt (I)}& ����. Ʊ�����Ѵ����������θĿ�\\
      {\tt N }&{\tt (I)}& ����. �Ѵ��ι�� ($N$)\\
      {\tt X }   & {\tt (D)} & ����. $\{x_j\}$�ޤ���$\{b_k\}$\\
                 &           & ����. $\{b_k\}$�ޤ���$\{x_j\}$\\
                 &           & �礭��\ttM$\times$\ttN ��2��������\\
      {\tt Y }   & {\tt (D)} & ����ΰ�. �礭��\ttM$\times$\ttN ��1��������\\
      {\tt IT}   & {\tt (I)} & ����ΰ�. �礭��5��1��������\\
      {\tt T }   & {\tt (D)} & ����ΰ�. �礭��5\ttN/2 ��1��������
    \end{tabular}
  \end{quote}

  \item �ǡ����γ�Ǽ��ˡ
  \begin{quote}
  
  {\tt X(M,N)}���������Ƥ�����, ��I�ˤĤ��ưʲ��Τ�
   ���˥ǡ�������Ǽ�����.

    \begin{tabular}{|c|c|c|c|c|}\hline
     \tt X(I,1) & \tt X(I,2) & 
     $\cdots$ & \tt X(I,N-1) & \tt X(I,N) \\\hline\hline
      $x_1$ & $x_2$ &
     $\cdots$ & $x_{N-1}$ & $x_N=0$ \\\hline
      $b_1$ & $b_2$ & 
     $\cdots$ & $b_{N-1}$ & $b_N=0$ \\\hline
    \end{tabular}
  \end{quote}
  
  \item ����
 
   \begin{itemize}
    \item ����{\tt X}��2�����ܤ��礭����, �Ѵ��ǡ������Τ�Τ��Ǽ������
          �Τ�ɬ�פ�{\tt N-1}��� 1�Ĥ����礭��{\tt N}�ȤȤ�ʤ���Фʤ��
	  �����Ȥ����դ�ɬ�פǤ���(������ʬ�Ϻ���ΰ�Ȥ��ƻȤ���).
    \end{itemize}

\end{enumerate}

\subsection{FTTCMI/FTTCMF/FTTCMB}

\begin{enumerate}

  \item ��ǽ 
  \begin{quote}
    ����$2\pi$�ζ��ؿ�$x(t)$��Ⱦ������$N$��ʬ����$N$�Ĥ�ɸ��
    $\{x_{j+1/2}\}$,
     $$x_{j+1/2}=x(\frac{\pi(j+1/2)}N), \quad j=0,1,\cdots,N-1 $$
    ��$M$��Ϳ����줿�Ȥ�, ���������ˤ��
    Υ����cosine�Ѵ�, �ޤ��Ϥ��ε��Ѵ���FFT�ˤ��Ԥʤ�. ������, 
    $N$�϶�����, ����$N/2=2^a3^b5^c(a,b,c: 0�ޤ��ϼ�����)$�Ǥ��뤳��.
  \end{quote}

  \item ���
    \begin{itemize}
     \item cosine���Ѵ�(��������)
      \begin{quote}
       $\{x_{j+1/2}\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{a_k\}$�����.
       $$a_k= \frac2N
              \sum^{N-1}_{j=0}x_{j+1/2}\cos\frac{\pi(j+1/2)k}N
       \quad (k=0,1,\cdots,N-1)$$
      \end{quote}

     \item cosine���Ѵ�(��������)
      \begin{quote}
       $\{a_k\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{x_{j+1/2}\}$�����.
       $$x_{j+1/2}=\frac12 a_0
              +\sum^{N-1}_{k=1}a_k\cos\frac{\pi(j+1/2)k}N
       \quad (j=0,1,\cdots,N-1)$$
      \end{quote}
     \end{itemize}    

  \item �ƤӽФ���ˡ 
  \begin{quote}
    {\tt FTTCMI(N,IT,T)}\\
    {\tt FTTCMF(M,N,X,Y,IT,T)}\\
    {\tt FTTCMB(M,N,X,Y,IT,T)}
  \end{quote}
  \item �ѥ�᡼���������� 
  \begin{quote}
    \begin{tabular}{llp{10cm}}
      {\tt M }&{\tt (I)}& ����. Ʊ�����Ѵ����������θĿ�\\
      {\tt N }&{\tt (I)}& ����. �Ѵ��ι�� ($N$)\\
      {\tt X }   & {\tt (D)} & ����. $\{x_{j+1/2}\}$�ޤ���$\{a_k\}$\\
                 &           & ����. $\{a_k\}$�ޤ���$\{x_{j+1/2}\}$\\
                 &           & �礭��\ttM$\times$\ttN ��2��������\\
      {\tt Y }   & {\tt (D)} & ����ΰ�. �礭��\ttM$\times$\ttN ��1��������\\
      {\tt IT}   & {\tt (I)} & ����ΰ�. �礭��5��1��������\\
      {\tt T }   & {\tt (D)} & ����ΰ�. �礭��6\ttN ��1��������
    \end{tabular}
  \end{quote}

  \item �ǡ����γ�Ǽ��ˡ
  \begin{quote}
  
  {\tt X(M,0:N-1)}���������Ƥ�����, ��I�ˤĤ��ưʲ��Τ�
   ���˥ǡ�������Ǽ�����.

    \begin{tabular}{|c|c|c|c|c|}\hline
     \tt X(I,0) & \tt X(I,1) & 
     $\cdots$ & \tt X(I,N-2) & \tt X(I,N-1) \\\hline\hline
      $x_{1/2}$ & $x_{3/2}$ & 
     $\cdots$ & $x_{N-3/2}$ & $x_{N-1/2}$ \\\hline
      $a_0$ & $a_1$ & 
     $\cdots$ & $a_{N-2}$ & $a_{N-1}$ \\\hline
    \end{tabular}
  \end{quote}
  
\end{enumerate}

\subsection{FTTSMI/FTTSMF/FTTSMB}

\begin{enumerate}

  \item ��ǽ 
  \begin{quote}
    ����$2\pi$�δ�ؿ�$x(t)$��Ⱦ������$N$��ʬ����$N$�Ĥ�ɸ��
    $\{x_{j+1/2}\}$,
     $$x_{j+1/2}=x(\frac{\pi(j+1/2)}N), \quad j=0,1,\cdots,N-1 $$
    ��$M$��Ϳ����줿�Ȥ�, ���������ˤ��
    Υ����sine�Ѵ�, �ޤ��Ϥ��ε��Ѵ���FFT�ˤ��Ԥʤ�. ������, 
    $N$�϶�����, ����$N/2=2^a3^b5^c(a,b,c: 0�ޤ��ϼ�����)$�Ǥ��뤳��.
  \end{quote}

  \item ���
    \begin{itemize}
     \item sine���Ѵ�(��������)
      \begin{quote}
       $\{x_{j+1/2}\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{b_k\}$�����.
       $$b_k= \frac2N
              \sum^{N-1}_{j=0}x_{j+1/2}\sin\frac{\pi(j+1/2)k}N
       \quad (k=1,2,\cdots,N)$$
      \end{quote}

     \item sine���Ѵ�(��������)
      \begin{quote}
       $\{b_k\}$�����Ϥ�, �����Ѵ���Ԥʤ�, $\{x_{j+1/2}\}$�����.
       $$x_{j+1/2}=\frac12 b_N(-1)^j
              +\sum^{N-1}_{k=1}b_k\sin\frac{\pi(j+1/2)k}N
       \quad (j=0,1,\cdots,N-1)$$
      \end{quote}
     \end{itemize}    

  \item �ƤӽФ���ˡ 
  \begin{quote}
    {\tt FTTSMI(N,IT,T)}\\
    {\tt FTTSMF(M,N,X,Y,IT,T)}\\
    {\tt FTTSMB(M,N,X,Y,IT,T)}
  \end{quote}
  \item �ѥ�᡼���������� 
  \begin{quote}
    \begin{tabular}{llp{10cm}}
      {\tt M }&{\tt (I)}& ����. Ʊ�����Ѵ����������θĿ�\\
      {\tt N }&{\tt (I)}& ����. �Ѵ��ι�� ($N$)\\
      {\tt X }   & {\tt (D)} & ����. $\{x_{j+1/2}\}$�ޤ���$\{b_k\}$\\
                 &           & ����. $\{b_k\}$�ޤ���$\{x_{j+1/2}\}$\\
                 &           & �礭��\ttM$\times$\ttN ��2��������\\
      {\tt Y }   & {\tt (D)} & ����ΰ�. �礭��\ttM$\times$\ttN ��1��������\\
      {\tt IT}   & {\tt (I)} & ����ΰ�. �礭��5��1��������\\
      {\tt T }   & {\tt (D)} & ����ΰ�. �礭��6\ttN ��1��������
    \end{tabular}
  \end{quote}

  \item �ǡ����γ�Ǽ��ˡ
  \begin{quote}
  
  {\tt X(M,N)}���������Ƥ�����, ��I�ˤĤ��ưʲ��Τ�
   ���˥ǡ�������Ǽ�����.

    \begin{tabular}{|c|c|c|c|c|}\hline
     \tt X(I,1) & \tt X(I,2) & 
     $\cdots$ & \tt X(I,N-1) & \tt X(I,N) \\\hline\hline
      $x_{1/2}$ & $x_{3/2}$ & 
     $\cdots$ & $x_{N-3/2}$ & $x_{N-1/2}$ \\\hline
      $b_1$ & $b_2$ & 
     $\cdots$ & $b_{N-1}$ & $b_N$ \\\hline
    \end{tabular}
  \end{quote}
  
\end{enumerate}


\end{document}
