# Patent

## Title
Method and apparatus for high-order PAPR reduction of an OFDM signal

## Abstract

A method and apparatus for high-order peak-to-average power ratio reduction of an OFDM signal are disclosed. The method partitions time-domain input data x[n] of length N into M disjoint subblocks in time domain, and a complete N-point transmitted signal {tilde over (x)}[n], n=0, 1, . . . , N−1, is composed after transformation, complex multiplication, and phase optimization, where M is a power of 2, M≧8 and N/M>1 is an integer. Accordingly, the apparatus comprises an N-point inverse fast Fourier transform (N-IFFT), a de-multiplexer, a transformer, two sets of memories, a plurality of complex multipliers, and an adder. This invention uses only one N-IFFT, whereby it achieves significant computation reduction. As M=8, the number of complex multiplications and that of memory units required are less than or equal to (N/2)log2N+(3N/4) and 3N/2, respectively. The invention also preserves the inherent property as well as advantages of an OFDM system.

## Background
FIELD OF THE INVENTION
The present invention generally relates to a method for solving the problem of peak-to-average power ratio (PAPR) of an orthogonal frequency division multiplexing (OFDM) signal at transmission side, and more specifically to a method for high-order PAPR reduction of an OFDM signal, and an apparatus of performing the same.
BACKGROUND OF THE INVENTION
Multicarrier communication systems such as discrete multitone (DMT) and OFDM systems have attracted much attention in the applications of high-speed communication. The advantages of the multicarrier communication system lie in partitioning a high speed data stream into a plurality of parallel data streams, each transmitted by a subcarrier. As such, each data stream is transmitted at low speed, and thus has a stronger capability in anti-multipath channel effect and narrow band interference.
FIG. 1 shows a block diagram of a conventional OFDM transmitter. In the OFDM transmitter, the input data X[k], k=0, 1, . . . , N−1, are transmitted in an OFDM symbol period, where N is the number of useful data in an OFDM symbol. After the serial/parallel transformation, N-point inverse fast Fourier transform (N-IFFT), and parallel/serial transformation, the input data are transformed into the following discrete time sequence:




  
    
      
        
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            =
            
              
                1
                
                  N
                
              
              ⁢
              
                
                  ∑
                  
                    k
                    =
                    0
                  
                  
                    N
                    -
                    1
                  
                
                ⁢
                
                  
                    X
                    ⁡
                    
                      [
                      k
                      ]
                    
                  
                  ⁢
                  
                    W
                    N
                    kn
                  
                
              
            
          
          ,
          
            
          
          ⁢
          
            n
            =
            0
          
          ,
          1
          ,
          ...
          ⁢
          
            
          
          ,
          
            N
            -
            1
          
        
        ⁢
        
          

        
        ⁢
        where
      
    
    
      
        (
        1
        )
      
    
  
  
    
      
        
          W
          N
        
        ≡
        
          e
          
            j2π
            /
            N
          
        
      
    
    
      
        (
        2
        )
      
    
  




is the twiddle factor. The discrete time sequence x[n] obtained from equation (1) undergoes the cyclic prefix insertion and digital/analog transformation to obtain an analog signal x(t). The analog signal x(t) is then transmitted to the RF front end for further processing, including an IQ modulation, an up conversion, and a power amplification. The PAPR of the analog signal x(t) is several dB higher than the PAPR of the corresponding discrete time sequence x[n], and is close to the PAPR of x[n/R]. where x[n/R] represents the sequence obtained by R times oversampling of x[n]. Therefore, the PAPR of x(t) can be approximated by using x[n/R] as follows:





  
    
      
        PAPR
        =
        
          
            
              max
              
                0
                ≤
                n
                ≤
                
                  RN
                  -
                  1
                
              
            
            ⁢
            
              
                
                
                  x
                  ⁡
                  
                    [
                    
                      n
                      /
                      R
                    
                    ]
                  
                
                
              
              2
            
          
          
            E
            ⁢
            
              {
              
                
                  
                  
                    x
                    ⁡
                    
                      [
                      
                        n
                        /
                        R
                      
                      ]
                    
                  
                  
                
                2
              
              }
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




Where E{·} is the expectation operation. The approximation is relatively accurate when R≧4. However, one of the main disadvantages of multicarrier communication systems is the high PAPR of the modulated signal. When the modulated signal with a high PAPR passes through the RF front end, the signal is distorted due to the non-linearity of a regular RF amplifier. The non-linearity not only causes the in-band signal distortion which leads to the increase of the bit error rate (BER), but also causes the out-of-band radiation which leads to the interference of adjacent channels, a violation of the government regulation. A straightforward solution to this problem would be using an RF amplifier with a larger linear range. However, the aforementioned solution will lead to the reduction of power efficiency, higher power consumption and a higher manufacturing cost.

There are several conventional methods for solving the aforementioned problem. Among these methods, the partial transmit sequences (PTS) is most attractive due to its relatively low realization complexity and capability in PAPR reduction. Ericsson (U.S. Pat. No. 6,125,103) disclosed a method for using PTS to solve the high PAPR of the signal at the OFDM transmission end, as shown in FIG. 2. The explanation is as follows.
First, the input data X[k] of length N is partitioned in the frequency domain into M disjoint subblocks, represented by X1[k], X2[k], . . . , XM[k], k=0, 1, . . . , N−1. The partition can be interleaved, adjacent, or irregular, as shown in FIG. 3 (using M=8 as an example). The M disjoint subblocks are phase-rotated and added to form the following signal:




  
    
      
        
          
            
              X
              ~
            
            ⁡
            
              [
              k
              ]
            
          
          =
          
            
              ∑
              
                m
                =
                1
              
              M
            
            ⁢
            
              
                b
                m
              
              ⁢
              
                
                  X
                  m
                
                ⁡
                
                  [
                  k
                  ]
                
              
            
          
        
        ,
        
          
        
        ⁢
        
          k
          =
          0
        
        ,
        1
        ,
        
          
        
        ⁢
        ...
        ⁢
        
          
        
        ,
        
          N
          -
          1
        
      
    
    
      
        (
        4
        )
      
    
  




where bm is the phase rotation parameter of the m-th subblock (mε{1, 2, . . . , M}) and |bm|=1.

Equation (4), after the N-IFFT, becomes:





  
    
      
        
          
            
              x
              ~
            
            ⁡
            
              [
              n
              ]
            
          
          =
          
            
              ∑
              
                m
                =
                1
              
              M
            
            ⁢
            
              
                b
                m
              
              ⁢
              
                
                  x
                  m
                
                ⁡
                
                  [
                  n
                  ]
                
              
            
          
        
        ,
        
          
        
        ⁢
        
          n
          =
          0
        
        ,
        1
        ,
        ...
        ⁢
        
          
        
        ,
        
          N
          -
          1
        
      
    
    
      
        (
        5
        )
      
    
  




where xm[n] is the result of the N-IFFT of the Xm[k]. In the PAPR reduction, the object of the PTS method is the phase optimization, i.e., seeking for the optimal sequence {b1, b2, . . . , bM} so that the PAPR of the transmitted signal is minimum. In practice, the phase of bm is usually restricted to one of the four possibilities {+1, −1, +j, −j} so that no multiplication operation is required in the phase rotation.

From FIG. 2, it can be seen that an N-point OFDM symbol requires M times of N-IFFT operation. That is, a total of M·(N/2)log2 N complex multiplications are required. Several methods are further devised to reduce the amount of computation required in the PTS method. Kang, Kim and Joo, in their article “A Novel Subblock Partition Scheme for Partial Transmit Sequence OFDM,” IEEE Trans. Broadcasting, vol. 45, no. 3, pp. 333-338, September 1999, disclosed a method of using the characteristics of the PTS interleaved partition of the subblocks, as shown in FIG. 4 (M=8). Each subblock has N points in the frequency domain, but only L points of them have non-zero values (L=N/M). Therefore, the N-IFTT on the N-point subblock Xm[k] is equivalent to the L-IFFT on the L-point subblock (where Xm[k] has non-zero values), repeating M times in the time domain to form the N-point signal, and multiplying the N-point signal with the N-point complex coefiicients:

(1/M)·ej2πmn/N, m=0, 1, . . . , M−1, n=0, 1, . . . , N−1

This method takes M·(L/2)log2 L+MN multiplications, and requires MN units of memory space.

Samsung (US. Patent publication 2003/0,067,866) disclosed a similar method, as shown in FIG. 5. The Samsung method differs from the previous method in no repetition after the L-IFFT on an L-point subblock. Instead, the multiplication of the L-point complex coefficients in the time domain is performed to make the time domain subblocks orthogonal so that the receiving end can separate each subblock. As there are only L points in each time domain subblock, the PAPR is lower and, therefore, the PAPR of the transmitted signal after the phase rotation and the addition is also lower. Although this method takes M·(L/2)log2 L+N multiplications and requires N units of memory space, this method reduces the length of the OFDM signal from N to L, which means that the capability of anti-multipath channel effect is also greatly reduced. Furthermore, the L-point complex coefficient multiplier to make the time domain subblocks orthogonal is hard to design and may not exist for most applications. This will further make the receiving end more difficult in obtaining the original transmitted data.
SUMMARY OF THE INVENTION
The present invention has been made to overcome the aforementioned drawback of the conventional PTS methods for PAPR reduction of the OFDM transmission end. The primary object of the present invention is to provide a high-order PAPR reduction method and apparatus for the OFDM signal.
The high-order PAPR reduction method according to the present invention includes the following steps: (1) using the N-IFFT to transform the frequency domain signal X[k] of length N into the time domain signal x[n] of length N, where N is the number of useful data in an OFDM symbol, and k, n=0, 1, . . . , N−1; (2) partitioning the time domain signal x[n] of length N into M disjoint subblocks, each subblock having the length of N/M, M being a power of 2, M being greater or equal to 8, and N/M being an integer greater than 1; (3) transforming the M subblocks into M sub-sequences zl[n], each having the length of N/M, where l=1, 2, . . . , M, and n=0, 1, . . . , (N/M)−1; (4) using fixed-phase rotation to rotate M sub-sequences zl[n] and obtain M sub-sequences {tilde over (z)}l[n], each having the length of N/M, where l=1, 2, . . . , M, and n=0, 1, . . . , (N/M)−1; and (5) using the phase rotation, phase optimization, and addition to obtain a complete N-point signal {tilde over (x)}[n] having the length of N.
Because not all the fixed-phase rotations require multiplier, the present invention of a high-order PAPR reduction apparatus for OFDM signal includes an N-point inverse fast Fourier transform (N-IFFT), a de-multiplexer, two set of memories, a transformer, at most M complex multipliers, and an adder. The N-IFFT transforms the input frequency domain signal X[k] into the time domain signal x[n]. The de-multiplexer uses the adjacent partitioning to partition x[n] into M disjoint subblocks of identical length. The transformer transforms the M disjoint subblocks into M sub-sequences zl[n] of length N/M, where l=1, 2, . . . , M and n=0, 1, . . . (N/M)−1. Some of the sub-sequences zl[n] are complex multiplied and phase rotated, and the remaining sub-sequences zl[n] are directly phase rotated. Finally, the adder adds them to obtain a complete N-point signal {tilde over (x)}[n].
For explanation, the present invention uses a preferred embodiment and a simplified embodiment of M=8.
The present invention only uses one N-IFFT so that the amount of computation is greatly reduced. In the preferred embodiment, the present invention takes (N/2)log2N+(3N/4) complex multiplications and requires 3N/2 units of memory space. In the simplified embodiment, the present invention takes (N/2)log2N complex multiplications and requires N units of memory space. But more important, the present invention keeps the original capability of anti-multipath channel effect in the OFDM system.
When M=8, the present invention shows different results in terms of computation amount and memory requirement, compared to the other three PTS methods. Compared to the original PTS method and the method disclosed by Kang, Kim and Joo, the simplified embodiment of the present invention and the Samsung's method use the least memory space. While the amount of multiplication is slightly higher or equal to that required by the Samsung's method, the present invention does not require shortening the length of the OFDM symbol, and therefore keeps the features and advantages of the OFDM system.
The foregoing and other objects, features, aspects and advantages of the present invention will become better understood from a careful reading of a detailed description provided herein below with appropriate reference to the accompanying drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows a schematic view of a conventional multicarrier communication system related to OFDM transmitter.
FIG. 2 shows a PTS method to solve the high PAPR problem of OFDM signal at transmission end.
FIG. 3 shows the three ways of partitioning the input data X[k] into subblocks using M=8.
FIG. 4 shows the embodiment of the method proposed by Kang, Kim and Joo to reduce the computation amount of PTS.
FIG. 5 shows the embodiment of the method proposed by Samsung to reduce the computation amount and memory requirement of PTS.
FIG. 6 shows a schematic view of a multi-stage time domain signal partitioning.
FIG. 7 shows a schematic view of 3-stage time domain signal partitioning when M=8.
FIG. 8 shows the high-order PAPR reduction method of OFDM signal of the present invention.
FIG. 9 shows the schematic view of the apparatus of the present invention for high-order PAPR reduction of the OFDM signal.
FIG. 10 shows an embodiment of the present invention in FIG. 9 when M=8.
FIG. 11 shows the transformer of FIG. 10.
FIG. 12(a) and FIG. 12(b) show the phase rotation parameter setting in FIG. 10.
FIG. 13 shows a simplified embodiment of the present invention when M=8.
FIG. 14 shows the transformer of FIG. 13.
FIG. 15(a) and FIG. 15(b) show the phase rotation parameter setting in FIG. 13.
FIG. 16 shows the comparison of the computation amount and the memory requirement between the present invention and the other three methods.



DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
FIG. 6 shows a schematic view of a multi-stage time domain signal partitioning having m stages. The number of time domain signals after partitioning is M=2m. The N-IFFT is performed on the frequency domain signal X[k] of length N to obtain a time domain signal x[n]. Assume the initial value to be:

y1(0)[n]=x[n]  (6)

At the first stage, the following equations can be used to partition x[n] into two disjoint signals:





  
    
      
        {
        
          
            
              
                
                  
                    y
                    1
                    
                      (
                      1
                      )
                    
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                =
                
                  
                    
                      y
                      1
                      
                        (
                        0
                        )
                      
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  +
                  
                    
                      y
                      1
                      
                        (
                        0
                        )
                      
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                N
                                2
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                
              
            
          
          
            
              
                
                  
                    y
                    2
                    
                      (
                      1
                      )
                    
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                =
                
                  
                    
                      y
                      1
                      
                        (
                        0
                        )
                      
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  -
                  
                    
                      y
                      1
                      
                        (
                        0
                        )
                      
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                N
                                2
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                
              
            
          
        
      
    
    
      
        (
        7
        )
      
    
  




where the notation ‘((n))N’ represents ‘(n modulo N)’, n=0, 1, . . . , N−1. In the same way, the two disjoint signals can be further partitioned into four disjoint signals. Repeating this step until the m-th stage, the following equations can be obtained for the M disjoint signals:





  
    
      
        {
        
          
            
              
                
                  
                    
                      y
                      1
                      
                        (
                        m
                        )
                      
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  =
                  
                    
                      
                        y
                        1
                        
                          (
                          
                            m
                            -
                            1
                          
                          )
                        
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    +
                    
                      
                        y
                        1
                        
                          (
                          
                            m
                            -
                            1
                          
                          )
                        
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  M
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      y
                      
                        
                          (
                          
                            M
                            /
                            2
                          
                          )
                        
                        +
                        1
                      
                      
                        (
                        m
                        )
                      
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  =
                  
                    
                      
                        y
                        1
                        
                          (
                          
                            m
                            -
                            1
                          
                          )
                        
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    -
                    
                      
                        y
                        1
                        
                          (
                          
                            m
                            -
                            1
                          
                          )
                        
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  M
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                
              
            
          
          ⁢
          
            

          
          ⁢
          
            {
            
              
                
                  
                    
                      
                        
                          y
                          2
                          
                            (
                            m
                            )
                          
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      =
                      
                        
                          
                            y
                            2
                            
                              (
                              
                                m
                                -
                                1
                              
                              )
                            
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        +
                        
                          
                            e
                            
                              j
                              ⁢
                              
                                
                                  2
                                  ⁢
                                  π
                                
                                M
                              
                            
                          
                          ·
                          
                            
                              y
                              2
                              
                                (
                                
                                  m
                                  -
                                  1
                                
                                )
                              
                            
                            ⁡
                            
                              [
                              
                                
                                  (
                                  
                                    (
                                    
                                      n
                                      -
                                      
                                        N
                                        M
                                      
                                    
                                    )
                                  
                                  )
                                
                                N
                              
                              ]
                            
                          
                        
                      
                    
                  
                
                
                  
                    
                      
                        
                          y
                          
                            
                              (
                              
                                M
                                /
                                2
                              
                              )
                            
                            +
                            2
                          
                          
                            (
                            m
                            )
                          
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      =
                      
                        
                          
                            y
                            2
                            
                              (
                              
                                m
                                -
                                1
                              
                              )
                            
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        -
                        
                          
                            e
                            
                              j
                              ⁢
                              
                                
                                  2
                                  ⁢
                                  π
                                
                                M
                              
                            
                          
                          ·
                          
                            
                              y
                              2
                              
                                (
                                
                                  m
                                  -
                                  1
                                
                                )
                              
                            
                            ⁡
                            
                              [
                              
                                
                                  (
                                  
                                    (
                                    
                                      n
                                      -
                                      
                                        N
                                        M
                                      
                                    
                                    )
                                  
                                  )
                                
                                N
                              
                              ]
                            
                          
                        
                      
                    
                  
                
              
              ⁢
              
                

              
              ⁢
              
                
              
              ⁢
              ⋮
              ⁢
              
                

              
              ⁢
              
                {
                
                  
                    
                      
                        
                          
                            y
                            
                              M
                              /
                              2
                            
                            
                              (
                              m
                              )
                            
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        =
                        
                          
                            
                              y
                              
                                M
                                /
                                2
                              
                              
                                (
                                
                                  m
                                  -
                                  1
                                
                                )
                              
                            
                            ⁡
                            
                              [
                              n
                              ]
                            
                          
                          +
                          
                            
                              e
                              
                                j
                                ⁢
                                
                                  
                                    2
                                    ⁢
                                    
                                      π
                                      ⁡
                                      
                                        (
                                        
                                          
                                            M
                                            2
                                          
                                          -
                                          1
                                        
                                        )
                                      
                                    
                                  
                                  M
                                
                              
                            
                            ·
                            
                              
                                y
                                
                                  M
                                  /
                                  2
                                
                                
                                  (
                                  
                                    m
                                    -
                                    1
                                  
                                  )
                                
                              
                              ⁡
                              
                                [
                                
                                  
                                    (
                                    
                                      (
                                      
                                        n
                                        -
                                        
                                          N
                                          M
                                        
                                      
                                      )
                                    
                                    )
                                  
                                  N
                                
                                ]
                              
                            
                          
                        
                      
                    
                  
                  
                    
                      
                        
                          
                            y
                            M
                            
                              (
                              m
                              )
                            
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        =
                        
                          
                            
                              y
                              
                                M
                                /
                                2
                              
                              
                                (
                                
                                  m
                                  -
                                  1
                                
                                )
                              
                            
                            ⁡
                            
                              [
                              n
                              ]
                            
                          
                          -
                          
                            
                              e
                              
                                j
                                ⁢
                                
                                  
                                    2
                                    ⁢
                                    
                                      π
                                      ⁡
                                      
                                        (
                                        
                                          
                                            M
                                            2
                                          
                                          -
                                          1
                                        
                                        )
                                      
                                    
                                  
                                  M
                                
                              
                            
                            ·
                            
                              
                                y
                                
                                  M
                                  /
                                  2
                                
                                
                                  (
                                  
                                    m
                                    -
                                    1
                                  
                                  )
                                
                              
                              ⁡
                              
                                [
                                
                                  
                                    (
                                    
                                      (
                                      
                                        n
                                        -
                                        
                                          N
                                          M
                                        
                                      
                                      )
                                    
                                    )
                                  
                                  N
                                
                                ]
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




This is the result of time domain signal partitioning required prior to the PTS phase rotation.

Based on the multi-stage signal partitioning of FIG. 6, FIG. 7 shows a schematic view of M=8. According to the previous procedure, the 3-stage partitioning for M=8 requires (N/2)log2(N)+2N multiplications, and 8N units of memory. Based on the same concept, the following description of a high-order PAPR reduction method for OFDM signals uses the symmetric characteristics of the M disjoint signals to lower the amount of multiplication and memory requirement.
Substituting equation (6) and the first stage equation (i.e., (7)) up to (m−1)th stage equation into equation (8), the M time domain input subblocks {x[n], n=0 ̃(N/M)−1}, {x[n], n=2N/M ̃(2N/M)−1}, . . . , {x[n], n=(M−1)N/M ̃N−1} can be obtained to represent M disjoint time domain signals. Using the symmetric characteristics to process the above subblocks, the method of high-order PAPR reduction for OFDM signals can be obtained, as shown in FIG. 8. First, the N-IFFT 801 is performed on the frequency domain signal X[k] of length N to obtain the time domain signal x[n] of length N. The adjacent partitioning is performed on x[n] to obtain M disjoint subblocks having the length N/M, where M is a power of 2, great or equal to 8, and N/M is an integer greater than 1, as in step 803. In step 805, a transformer is used to transform the M disjoint subblocks into M sub-sequences zl[n], each having the length N/M, l=1, 2, . . . , M and n=0, 1, . . . , (N/M)−1. In step 807, the fixed-phase rotation is used to rotate the M sub-sequences zl[n] to obtain M sub-seuqneces {tilde over (z)}l[n], each having the length of N/M, =1, 2, . . . , M and n=0, 1, . . . , (N/M)−1. Finally, in step 809, the M sub-sequences {tilde over (z)}l[n], after phase rotation and phase optimization, are added to form a complete N-point transmitted signal {tilde over (x)}[n], where n=0, 1, . . . , N−1.
In step 807, not all of the fixed-phase rotations require a complex multiplier, therefore, FIG. 9 shows a schematic view of a preferred embodiment of a high-order PAPR reduction apparatus of the present invention. The apparatus includes an N-IFFT 801, a de-multiplexer 903, two sets of memories 905, 909, a transformer 907, at most M complex multipliers (for fixed-phase rotations), and an adder 911. N-IFFT 801 transforms the input frequency domain signal X[k] into the time domain signal x[n]. De-multiplexer 903 partitions x[n] into M adjacent, yet disjoint, subblocks {x[n], n=0 ̃(N/M)−1}{grave over ( )}{x[n], n=N/M ̃(2N/M)−1}, . . . , {x[n], n=(M−1)N/M ̃N−1} of the identical length N/M, stored in memory 905. The M subblocks are transformed by transformer 907 into M sub-sequences zl[n], each having length N/M, l=1, 2, . . . , M and n=0, 1, . . . , (N/M)−1, also stored in memory 905. Some of the M sub-sequences zl[n] are passed through complex multiplier ejθl to form another sub-sequences {tilde over (z)}l[n], stored in memory 909, where l is between 1 and M, n=0, 1, . . . , (N/M)−1. The next step is to select sub-sequence z[n] or {tilde over (z)}l[n] for phase rotation according to different time period. Finally, adder 911 adds them to form a complete N-point signal {tilde over (x)}[n], where n=0, 1, . . . , N−1.
Using M=8 as an example, FIG. 10 shows a schematic view. The input signal X[k] is transformed into x[n] by N-IFFT 801. De-multiplezer 1003 takes x[n], n=0, 1, . . . , N−1 and partitions into eight subblocks {x[n], n=0 ̃(N/8)−1}, {x[n], n=N/8 ̃(2N/8)−1}, . . . , {x[n], n=7N/8 ̃N−1}, each having length N/8, stored in memory 1005. Transformer 1007 transforms the eight subblocks into eight sub-sequences z1[n], z2[n], . . . , z8[n]. According equations (6), (7), and (8), the following equations can be obtained:




  
    
      
        
          
            z
            1
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        2
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        4
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          4
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        8
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        5
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        7
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
        
      
    
    
      
        (
        
          9
          ⁢
          a
        
        )
      
    
  
  
    
      
        
          
            z
            5
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        2
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        4
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          4
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        8
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        5
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        7
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
        
      
    
    
      
        (
        
          9
          ⁢
          b
        
        )
      
    
  
  
    
      
        
          
            z
            3
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        2
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        4
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          4
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        8
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        5
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        7
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
        
      
    
    
      
        (
        
          9
          ⁢
          c
        
        )
      
    
  
  
    
      
        
          
            z
            7
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        2
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        4
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          4
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        8
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        5
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        7
                        ⁢
                        
                          N
                          /
                          8
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
        
      
    
    
      
        (
        
          9
          ⁢
          d
        
        )
      
    
  
  
    
      
        
          
            z
            2
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        2
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        4
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          4
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            
              e
              
                j
                ⁢
                
                  π
                  4
                
              
            
            ⁢
            
              {
              
                
                  x
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              N
                              /
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                -
                
                  x
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              5
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                +
                
                  jx
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              3
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                -
                
                  jx
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              7
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
              
              }
            
          
        
      
    
    
      
        (
        
          9
          ⁢
          e
        
        )
      
    
  
  
    
      
        
          
            z
            6
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        2
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        4
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          4
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            
              e
              
                j
                ⁢
                
                  π
                  4
                
              
            
            ⁢
            
              {
              
                
                  -
                  
                    x
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                N
                                /
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                
                +
                
                  x
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              5
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                -
                
                  jx
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              3
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                +
                
                  jx
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              7
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
              
              }
            
          
        
      
    
    
      
        (
        
          9
          ⁢
          f
        
        )
      
    
  
  
    
      
        
          
            z
            4
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        2
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        4
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          4
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            
          
          ⁢
          
            
              e
              
                j
                ⁢
                
                  π
                  4
                
              
            
            ⁢
            
              {
              
                
                  jx
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              N
                              /
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                -
                
                  jx
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              5
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                +
                
                  x
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              3
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                -
                
                  x
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              7
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
              
              }
            
          
        
      
    
    
      
        (
        
          9
          ⁢
          g
        
        )
      
    
  
  
    
      
        
          
            z
            8
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          -
          
            x
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        2
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          -
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        N
                        /
                        4
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  (
                  
                    (
                    
                      n
                      -
                      
                        3
                        ⁢
                        
                          N
                          /
                          4
                        
                      
                    
                    )
                  
                  )
                
                N
              
              ]
            
          
          +
          
            
          
          ⁢
          
            
              e
              
                j
                ⁢
                
                  π
                  4
                
              
            
            ⁢
            
              {
              
                
                  -
                  
                    jx
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                N
                                /
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                
                +
                
                  jx
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              5
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                -
                
                  x
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              3
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                +
                
                  x
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            -
                            
                              7
                              ⁢
                              
                                N
                                /
                                8
                              
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
              
              }
            
          
        
      
    
    
      
        (
        
          9
          ⁢
          h
        
        )
      
    
  




Accordingly, a schematic view of transformer 1007 of FIG. 10 can be shown in FIG. 11. As shown in FIG. 11, transformer 1007 uses 24 adders, 3 imagery j multipliers, and 2 complex multipliers to implement equations (9a)-(9h). It has a similar structure as 8-IFFT. It can be proven that the sub-sequences z1[n], z2[n], . . . , z8[n] in equations (9a)-(9h) are identical to the time sequences x1[n], x2[n], . . . , x8[n] obtained from the original PTS method shown in FIG. 2. Therefore, equation (5) can be rewritten as:





  
    
      
        
          
            
              x
              ~
            
            ⁡
            
              [
              n
              ]
            
          
          =
          
            
              ∑
              
                l
                =
                1
              
              8
            
            ⁢
            
              
                b
                l
              
              ⁢
              
                
                  z
                  l
                
                ⁡
                
                  [
                  n
                  ]
                
              
            
          
        
        ,
        
          
        
        ⁢
        
          n
          =
          0
        
        ,
        1
        ,
        ...
        ⁢
        
          
        
        ,
        
          N
          -
          1
        
      
    
    
      
        (
        10
        )
      
    
  




Assuming equations (11a)-(11d) as follows:





  
    
      
        
          
            
              z
              ~
            
            2
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            e
            
              j
              ⁢
              
                π
                4
              
            
          
          ·
          
            
              z
              2
            
            ⁡
            
              [
              n
              ]
            
          
        
      
    
    
      
        (
        
          11
          ⁢
          a
        
        )
      
    
  
  
    
      
        
          
            
              z
              ~
            
            4
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            e
            
              j
              ⁢
              
                π
                4
              
            
          
          ·
          
            
              z
              4
            
            ⁡
            
              [
              n
              ]
            
          
        
      
    
    
      
        (
        
          11
          ⁢
          b
        
        )
      
    
  
  
    
      
        
          
            
              z
              ~
            
            6
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            e
            
              j
              ⁢
              
                π
                4
              
            
          
          ·
          
            
              z
              6
            
            ⁡
            
              [
              n
              ]
            
          
        
      
    
    
      
        (
        
          11
          ⁢
          c
        
        )
      
    
  
  
    
      
        
          
            
              z
              ~
            
            8
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            e
            
              j
              ⁢
              
                π
                4
              
            
          
          ·
          
            
              z
              8
            
            ⁡
            
              [
              n
              ]
            
          
        
      
    
    
      
        (
        
          11
          ⁢
          d
        
        )
      
    
  




and using equations (9a)-(9h) and equations (11a)-(11d), the following symmetry can be obtained, that is the relationship between the sub-sequences {z1[((n+pN/8))N], z2[((n+pN/8))N], . . . , z8[((n+pN/8))N]} having different time shift and the sub-sequences {z1[n], z2[n], . . . , z8[n]}.





  
    
      
        
          
            p
            =
            1
          
          ,
          
            n
            =
            
              
                pN
                /
                
                  8
                  ~
                  
                    [
                    
                      
                        (
                        
                          p
                          +
                          1
                        
                        )
                      
                      ⁢
                      
                        N
                        /
                        8
                      
                    
                    ]
                  
                
              
              -
              
                1
                ⁢
                
                  :
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      z
                      1
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    7
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    7
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          e
                          
                            j
                            ⁢
                            
                              π
                              4
                            
                          
                        
                        ⁢
                        
                          
                            z
                            2
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          
                            z
                            ~
                          
                          2
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      3
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    7
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        jz
                        3
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    7
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          je
                          
                            j
                            ⁢
                            
                              π
                              4
                            
                          
                        
                        ⁢
                        
                          
                            z
                            4
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        j
                        ⁢
                        
                          
                            
                              z
                              ~
                            
                            4
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      5
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    7
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          5
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      6
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        6
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    7
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          -
                          
                            e
                            
                              j
                              ⁢
                              
                                π
                                4
                              
                            
                          
                        
                        ⁢
                        
                          
                            z
                            6
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        -
                        
                          
                            
                              z
                              ~
                            
                            6
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      7
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    7
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          jz
                          7
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      8
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        8
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    7
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          -
                          
                            je
                            
                              j
                              ⁢
                              
                                π
                                4
                              
                            
                          
                        
                        ⁢
                        
                          
                            z
                            8
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                            
                              z
                              ~
                            
                            8
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        12
        )
      
    
  
  
    
      
        
          
            p
            =
            2
          
          ,
          
            n
            =
            
              
                pN
                /
                
                  8
                  ~
                  
                    [
                    
                      
                        (
                        
                          p
                          +
                          1
                        
                        )
                      
                      ⁢
                      
                        N
                        /
                        8
                      
                    
                    ]
                  
                
              
              -
              
                1
                ⁢
                
                  :
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      z
                      1
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    6
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    6
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        jz
                        2
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      3
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    6
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          3
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    6
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          jz
                          4
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      5
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    6
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      6
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        6
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    6
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        jz
                        6
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      7
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    6
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          7
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      8
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        8
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    6
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          jz
                          8
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        13
        )
      
    
  
  
    
      
        
          
            p
            =
            3
          
          ,
          
            n
            =
            
              
                pN
                /
                
                  8
                  ~
                  
                    [
                    
                      
                        (
                        
                          p
                          +
                          1
                        
                        )
                      
                      ⁢
                      
                        N
                        /
                        8
                      
                    
                    ]
                  
                
              
              -
              
                1
                ⁢
                
                  :
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      z
                      1
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    5
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    5
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          je
                          
                            j
                            ⁢
                            
                              π
                              4
                            
                          
                        
                        ⁢
                        
                          
                            z
                            2
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          
                            jz
                            ~
                          
                          2
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      3
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    5
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          jz
                          3
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    5
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          e
                          
                            j
                            ⁢
                            
                              π
                              4
                            
                          
                        
                        ⁢
                        
                          
                            z
                            4
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          
                            z
                            ~
                          
                          4
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      5
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    5
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          5
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      6
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        6
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    5
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          -
                          
                            je
                            
                              j
                              ⁢
                              
                                π
                                4
                              
                            
                          
                        
                        ⁢
                        
                          
                            z
                            6
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                            
                              z
                              ~
                            
                            6
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      7
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    5
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        jz
                        7
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      8
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        8
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    5
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          -
                          
                            e
                            
                              j
                              ⁢
                              
                                π
                                4
                              
                            
                          
                        
                        ⁢
                        
                          
                            z
                            8
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        -
                        
                          
                            
                              z
                              ~
                            
                            8
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        14
        )
      
    
  
  
    
      
        
          
            p
            =
            4
          
          ,
          
            n
            =
            
              
                pN
                /
                
                  8
                  ~
                  
                    [
                    
                      
                        (
                        
                          p
                          +
                          1
                        
                        )
                      
                      ⁢
                      
                        N
                        /
                        8
                      
                    
                    ]
                  
                
              
              -
              
                1
                ⁢
                
                  :
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      z
                      1
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    4
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    4
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          2
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      3
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    4
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    4
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          4
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      5
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    4
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      6
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        6
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    4
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          6
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      7
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    4
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      8
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        8
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    4
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          8
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        15
        )
      
    
  
  
    
      
        
          
            p
            =
            5
          
          ,
          
            n
            =
            
              
                pN
                /
                
                  8
                  ~
                  
                    [
                    
                      
                        (
                        
                          p
                          +
                          1
                        
                        )
                      
                      ⁢
                      
                        N
                        /
                        8
                      
                    
                    ]
                  
                
              
              -
              
                1
                ⁢
                
                  :
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      z
                      1
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    3
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    3
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          -
                          
                            e
                            
                              j
                              ⁢
                              
                                π
                                4
                              
                            
                          
                        
                        ⁢
                        
                          
                            z
                            2
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        -
                        
                          
                            
                              z
                              ~
                            
                            2
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      3
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    3
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        jz
                        3
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    3
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          -
                          
                            je
                            
                              j
                              ⁢
                              
                                π
                                4
                              
                            
                          
                        
                        ⁢
                        
                          
                            z
                            4
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                            
                              z
                              ~
                            
                            4
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      5
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    3
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          5
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      6
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        6
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    3
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          e
                          
                            j
                            ⁢
                            
                              π
                              4
                            
                          
                        
                        ⁢
                        
                          
                            z
                            6
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          
                            z
                            ~
                          
                          6
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      7
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    3
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          jz
                          7
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      8
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        8
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    3
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          je
                          
                            j
                            ⁢
                            
                              π
                              4
                            
                          
                        
                        ⁢
                        
                          
                            z
                            8
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        j
                        ⁢
                        
                          
                            
                              z
                              ~
                            
                            8
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        16
        )
      
    
  
  
    
      
        
          
            p
            =
            6
          
          ,
          
            n
            =
            
              
                pN
                /
                
                  8
                  ~
                  
                    [
                    
                      
                        (
                        
                          p
                          +
                          1
                        
                        )
                      
                      ⁢
                      
                        N
                        /
                        8
                      
                    
                    ]
                  
                
              
              -
              
                1
                ⁢
                
                  :
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      z
                      1
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    2
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    2
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          jz
                          2
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      3
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    2
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          3
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    2
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        jz
                        4
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      5
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    2
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      6
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        6
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    2
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          jz
                          6
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      7
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    2
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          7
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      8
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        8
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  
                                    2
                                    ⁢
                                    N
                                  
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        jz
                        8
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        17
        )
      
    
  
  
    
      
        
          
            p
            =
            7
          
          ,
          
            n
            =
            
              
                pN
                /
                
                  8
                  ~
                  
                    [
                    
                      
                        (
                        
                          p
                          +
                          1
                        
                        )
                      
                      ⁢
                      
                        N
                        /
                        8
                      
                    
                    ]
                  
                
              
              -
              
                1
                ⁢
                
                  :
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          {
          
            
              
                
                  
                    
                      z
                      1
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  7
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  7
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          -
                          
                            je
                            
                              j
                              ⁢
                              
                                π
                                4
                              
                            
                          
                        
                        ⁢
                        
                          
                            z
                            2
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                            
                              z
                              ~
                            
                            2
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      3
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  7
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          jz
                          3
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  7
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          -
                          
                            e
                            
                              j
                              ⁢
                              
                                π
                                4
                              
                            
                          
                        
                        ⁢
                        
                          
                            z
                            4
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        -
                        
                          
                            
                              z
                              ~
                            
                            4
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      5
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  7
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      -
                      
                        
                          z
                          5
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      6
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  7
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        6
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          je
                          
                            j
                            ⁢
                            
                              π
                              4
                            
                          
                        
                        ⁢
                        
                          
                            z
                            6
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        j
                        ⁢
                        
                          
                            
                              z
                              ~
                            
                            6
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      7
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  7
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        jz
                        7
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
            
              
                
                  
                    
                      z
                      8
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                
                                  7
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      
                        z
                        8
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                -
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                    =
                    
                      
                        
                          e
                          
                            j
                            ⁢
                            
                              π
                              4
                            
                          
                        
                        ⁢
                        
                          
                            z
                            8
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                      
                      =
                      
                        
                          
                            z
                            ~
                          
                          8
                        
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




It can be seen from equations (12)-(18) that transformer 1007 only needs to form N/8-length sub-sequences z1[n], z2[n], z3[n], z4[n], z5[n], z6[n], z7[n], z8[n] and obtain {tilde over (z)}2[n], {tilde over (z)}4[n], {tilde over (z)}6[n], {tilde over (z)}8[n], n=0, . . . (N/8)−1. As the eight subblocks {x[n], n=0, . . . , (N/8)−1}, {x[n], n=N/8, . . . , 2N/8}−1}, . . . , {x[n], n=7N/8, . . . , N−1} are no longer needed, the eight memory blocks having N/8 units each in memory 1005 can be released to store z1[n], z2[n], . . . , z8[n]′n=0, . . . , (N/8)−1. In other words, the required memory is 8×(N/8)+4×(N/8)=3N/2 units. Finally substituting equations (12)-(18) into equation (10), the following two results can be obtained:

    Result 1: p=0, 2, 4, 6, n=0, . . . , (N/8)−1






  
    
      
        
          
            x
            ~
          
          ⁡
          
            [
            
              n
              +
              
                pN
                8
              
            
            ]
          
        
        =
        
          
            ∑
            
              l
              =
              1
            
            8
          
          ⁢
          
            
              
                b
                ~
              
              l
            
            ·
            
              z
              l
            
          
        
      
    
    
      
        (19a)
      
    
  




where the phase rotation parameter {tilde over (b)}l is shown in FIG. 12(a).

    Result 2: p=1, 3, 5, 7, n=0, . . . , (N/8)−1






  
    
      
        
          
            x
            ~
          
          ⁡
          
            [
            
              n
              +
              
                pN
                8
              
            
            ]
          
        
        =
        
          
            
              ∑
              
                l
                =
                1
              
              4
            
            ⁢
            
              
                
                  b
                  ~
                
                
                  
                    2
                    ⁢
                    l
                  
                  -
                  1
                
              
              ·
              
                z
                
                  
                    2
                    ⁢
                    l
                  
                  -
                  1
                
              
            
          
          +
          
            
              ∑
              
                l
                =
                1
              
              4
            
            ⁢
            
              
                
                  b
                  ~
                
                
                  2
                  ⁢
                  l
                
              
              ·
              
                
                  z
                  ~
                
                
                  2
                  ⁢
                  l
                
              
            
          
        
      
    
    
      
        (19b)
      
    
  




where the phase rotation parameter {tilde over (b)}l is shown in FIG. 12(b).
Refer to FIG. 10, after the phase rotation of the eight sub-sequences {z1[n], z2[n], . . . , z8[n]}, n=0, . . . , (N/8)−1, adder 1011 adds them to form the N/8-length transmitted signal {{tilde over (x)}[0], {tilde over (x)}[1], . . . , [(N/8)−1]}. By using different phase rotation parameter {tilde over (b)}l, the eight sub-sequences {z1[n], z3[n], z5[n], z7[n]} and {{tilde over (z)}2[n], {tilde over (z)}4[n], {tilde over (z)}6[n], {tilde over (z)}8[n]} can be used to obtain the next transmitted signal {{tilde over (x)}[N/8], {tilde over (x)}[(N/8)+1], . . . , x[(2N/8)−1]}. By the same way, the entire N-point transmitted signal {tilde over (x)}[n] can be obtained.
As shown in FIG. 10 and FIG. 11, when {tilde over (b)}l is +1, −1, +j, or −j, the multiplications that present invention requires come from N-IFFT 801, transformer 1007 (including two complex multipliers), and four complex multipliers (for fixed-phase rotations). Therefore, the total amount of complex multiplications is (N/2)log2N+2×(N/8)+4×(N/8)=(N/2)log2N+(3N/4), and the memory requirement is 3N/2 units.
The following description uses M=8 as an example to explain the simplified embodiment of the high-order PAPR reduction apparatus of the present invention. By losing a slight capability for PAPR reduction, a smaller amount of multiplications and memory requirement can be achieved. FIG. 13 shows a schematic view of the simplified embodiment. The frequency domain sequence X[k] is transformed by N-IFFT 801 into time domain signal sequence x[n]. De-multiplexer 1003 partitions x[n], n=0, 1, . . . , N−1 into 8 subblocks {x[n], n=0, . . . , (N/8)−1}, {x[n], n=N/8, . . . , (2N/8)−1}, . . . , {x[n], n=7N/8, . . . , N−1}, each having the length N/8, and stores them into 8 N/8-length blocks in memory 1005. Substituting equations (9a)-(9h) into equation (10), the following equation can be obtained:




  
    
      
        
          
            x
            ~
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            ·
            
              (
              
                
                  b
                  1
                
                +
                
                  b
                  5
                
                +
                
                  b
                  3
                
                +
                
                  b
                  7
                
                +
                
                  b
                  2
                
                +
                
                  b
                  6
                
                +
                
                  b
                  4
                
                +
                
                  b
                  8
                
              
              )
            
          
          +
          
            
              x
              ⁡
              
                [
                
                  
                    (
                    
                      (
                      
                        N
                        -
                        
                          N
                          2
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            ·
            
              (
              
                
                  b
                  1
                
                +
                
                  b
                  5
                
                +
                
                  b
                  3
                
                +
                
                  b
                  7
                
                -
                
                  b
                  2
                
                -
                
                  b
                  6
                
                -
                
                  b
                  4
                
                -
                
                  b
                  8
                
              
              )
            
          
          +
          
            
              x
              ⁡
              
                [
                
                  
                    (
                    
                      (
                      
                        N
                        -
                        
                          N
                          4
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            ·
            
              (
              
                
                  b
                  1
                
                +
                
                  b
                  5
                
                -
                
                  b
                  3
                
                -
                
                  b
                  7
                
                +
                
                  jb
                  2
                
                +
                
                  jb
                  6
                
                -
                
                  jb
                  4
                
                -
                
                  jb
                  8
                
              
              )
            
          
          +
          
            
              x
              ⁡
              
                [
                
                  
                    (
                    
                      (
                      
                        N
                        -
                        
                          
                            3
                            ⁢
                            N
                          
                          4
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            ·
            
              (
              
                
                  b
                  1
                
                +
                
                  b
                  5
                
                -
                
                  b
                  3
                
                -
                
                  b
                  7
                
                -
                
                  jb
                  2
                
                -
                
                  jb
                  6
                
                +
                
                  jb
                  4
                
                +
                
                  jb
                  8
                
              
              )
            
          
          +
          
            
              x
              ⁡
              
                [
                
                  
                    (
                    
                      (
                      
                        N
                        -
                        
                          N
                          8
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            ·
            
              {
              
                
                  b
                  1
                
                -
                
                  b
                  5
                
                +
                
                  jb
                  3
                
                -
                
                  jb
                  7
                
                +
                
                  
                    e
                    
                      j
                      ⁢
                      
                        π
                        4
                      
                    
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        2
                      
                      -
                      
                        b
                        6
                      
                    
                    )
                  
                
                +
                
                  
                    je
                    
                      j
                      ⁢
                      
                        π
                        4
                      
                    
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        4
                      
                      -
                      
                        b
                        8
                      
                    
                    )
                  
                
              
              }
            
          
          +
          
            
              x
              ⁡
              
                [
                
                  
                    (
                    
                      (
                      
                        N
                        -
                        
                          N
                          8
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            ·
            
              {
              
                
                  b
                  1
                
                -
                
                  b
                  5
                
                +
                
                  jb
                  3
                
                -
                
                  jb
                  7
                
                -
                
                  
                    e
                    
                      j
                      ⁢
                      
                        π
                        4
                      
                    
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        2
                      
                      -
                      
                        b
                        6
                      
                    
                    )
                  
                
                -
                
                  
                    je
                    
                      j
                      ⁢
                      
                        π
                        4
                      
                    
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        4
                      
                      -
                      
                        b
                        8
                      
                    
                    )
                  
                
              
              }
            
          
          +
          
            
              x
              ⁡
              
                [
                
                  
                    (
                    
                      (
                      
                        N
                        -
                        
                          
                            3
                            ⁢
                            N
                          
                          8
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            ·
            
              {
              
                
                  b
                  1
                
                -
                
                  b
                  5
                
                -
                
                  jb
                  3
                
                +
                
                  jb
                  7
                
                +
                
                  
                    je
                    
                      j
                      ⁢
                      
                        π
                        4
                      
                    
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        2
                      
                      -
                      
                        b
                        6
                      
                    
                    )
                  
                
                +
                
                  
                    e
                    
                      j
                      ⁢
                      
                        π
                        4
                      
                    
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        4
                      
                      -
                      8
                    
                    )
                  
                
              
              }
            
          
          +
          
            
              x
              ⁡
              
                [
                
                  
                    (
                    
                      (
                      
                        N
                        -
                        
                          
                            7
                            ⁢
                            N
                          
                          8
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            ·
            
              {
              
                
                  b
                  1
                
                -
                
                  b
                  5
                
                +
                
                  jb
                  3
                
                +
                
                  jb
                  7
                
                -
                
                  
                    je
                    
                      j
                      ⁢
                      
                        π
                        4
                      
                    
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        2
                      
                      -
                      
                        b
                        6
                      
                    
                    )
                  
                
                -
                
                  
                    e
                    
                      j
                      ⁢
                      
                        π
                        4
                      
                    
                  
                  ⁡
                  
                    (
                    
                      
                        b
                        4
                      
                      -
                      
                        b
                        8
                      
                    
                    )
                  
                
              
              }
            
          
        
      
    
    
      
        (
        20
        )
      
    
  




Equation (20) shows that when b2=b6 and b4=b8, it does not require complex multiplication to compute equation (20). Under such circumstances, using equations (9a)-(9h) to express equation (20) as following:




  
    
      
        
          
            x
            ~
          
          ⁢
          
            
          
          [
          n
          ]
        
        =
        
          
            
              b
              1
            
            ⁢
            
              
                z
                1
              
              ⁡
              
                [
                n
                ]
              
            
          
          +
          
            
              b
              5
            
            ⁢
            
              
                z
                5
              
              ⁡
              
                [
                n
                ]
              
            
          
          +
          
            
              b
              3
            
            ⁢
            
              
                z
                3
              
              ⁡
              
                [
                n
                ]
              
            
          
          +
          
            
              b
              7
            
            ⁢
            
              
                z
                7
              
              ⁡
              
                [
                n
                ]
              
            
          
          +
          
            
              b
              2
            
            ·
            
              {
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                +
                
                  j
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                
              
              }
            
          
          +
          
            
              b
              4
            
            ·
            
              {
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                -
                
                  j
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                
              
              }
            
          
        
      
    
    
      
        (
        21
        )
      
    
  
  
    
      where
    
    
      
        
      
    
  
  
    
      
        
          
            w
            2
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          2
          ·
          
            {
            
              
                x
                ⁢
                
                  
                
                [
                n
                ]
              
              -
              
                x
                ⁢
                
                  
                
                [
                
                  
                    (
                    
                      (
                      
                        n
                        -
                        
                          N
                          2
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            }
          
        
      
    
    
      
        (22a)
      
    
  
  
    
      
        
          
            w
            4
          
          ⁡
          
            [
            n
            ]
          
        
        =
        
          2
          ·
          
            {
            
              
                x
                ⁢
                
                  
                
                [
                
                  
                    (
                    
                      (
                      
                        n
                        -
                        
                          N
                          4
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
              -
              
                x
                ⁢
                
                  
                
                [
                
                  
                    (
                    
                      (
                      
                        n
                        -
                        
                          
                            3
                            ⁢
                            N
                          
                          4
                        
                      
                      )
                    
                    )
                  
                  N
                
                ]
              
            
            }
          
        
      
    
    
      
        (22b)
      
    
  




Based on equations (21) and (12), the following is obtained:





  
    
      
        
          
            x
            ~
          
          ⁡
          
            [
            
              
                (
                
                  (
                  
                    n
                    +
                    
                      N
                      8
                    
                  
                  )
                
                )
              
              N
            
            ]
          
        
        =
        
          
            
              b
              1
            
            ⁢
            
              
                z
                1
              
              ⁡
              
                [
                n
                ]
              
            
          
          -
          
            
              b
              5
            
            ⁢
            
              
                z
                5
              
              ⁡
              
                [
                n
                ]
              
            
          
          +
          
            
              jb
              3
            
            ⁢
            
              
                z
                3
              
              ⁡
              
                [
                n
                ]
              
            
          
          -
          
            
              jb
              7
            
            ⁢
            
              
                z
                7
              
              ⁡
              
                [
                n
                ]
              
            
          
          +
          
            
              b
              2
            
            ·
            
              {
              
                
                  
                    w
                    2
                  
                  ⁢
                  
                    {
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              N
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                +
                
                  
                    jw
                    4
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              N
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
              
              }
            
          
          +
          
            
              b
              4
            
            ·
            
              {
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              N
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                -
                
                  
                    jw
                    4
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              n
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
              
              }
            
          
        
      
    
    
      
        (
        23
        )
      
    
  




Furthermore, the symmetric relationship can be obtained from equations (22a) and (22b):





  
    
      
        {
        
          
            
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                2
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    -
                    
                      
                        w
                        4
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
          
          
            
              
                
                  
                    w
                    4
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                2
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  6
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                
              
            
          
        
      
    
    
      
        (24a)
      
    
  
  
    
      
        {
        
          
            
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                3
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    -
                    
                      
                        w
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                +
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                
              
            
          
          
            
              
                
                  
                    w
                    4
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                3
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  5
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                
              
            
          
        
      
    
    
      
        (24b)
      
    
  
  
    
      
        {
        
          
            
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                4
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    -
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
          
          
            
              
                
                  
                    w
                    4
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                4
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  4
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    -
                    
                      
                        w
                        4
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (24c)
      
    
  
  
    
      
        {
        
          
            
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                5
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    -
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                +
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                
              
            
          
          
            
              
                
                  
                    w
                    4
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                5
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  3
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    -
                    
                      
                        w
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                +
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (24d)
      
    
  
  
    
      
        {
        
          
            
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                6
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                
              
            
          
          
            
              
                
                  
                    w
                    4
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                6
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                
                                  2
                                  ⁢
                                  N
                                
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    -
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (24e)
      
    
  
  
    
      
        {
        
          
            
              
                
                  
                    w
                    2
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                7
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      2
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              +
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                
              
            
          
          
            
              
                
                  
                    w
                    4
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              
                                7
                                ⁢
                                N
                              
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                  
                    
                      w
                      4
                    
                    ⁡
                    
                      [
                      
                        
                          (
                          
                            (
                            
                              n
                              -
                              
                                N
                                8
                              
                            
                            )
                          
                          )
                        
                        N
                      
                      ]
                    
                  
                  =
                  
                    -
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                +
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        
          24
          ⁢
          f
        
        )
      
    
  




Based on equations (21), (23), and (24a)-(24f), the transmitted signal {tilde over (x)}[n] is composed of sub-sequences {z1[n], z3[n], z5[n], z7[n]} and {w2[n], w4[n], w2[((n+N/8))N], w4[((n+N/8))N]}. Therefore, transformer 1307 is to transform the eight N/8-length subblocks {x[n], n=0, . . . , (N/8)−1}, {x[n], n=N/8, . . . , (2N/8)−1}, . . . , {x[n], n=7N/8, . . . , N−1} into eight sub-sequences {z1[n], z3[n], z5[n], z7[n]} and {w2[n], w4[n], w2[((n+N/8))N], w4[((n+N/8))N]}. According to equations (9a)-(9d), (22a) and (22b), a schematic view of transformer 1307 of FIG. 13 can be shown in FIG. 14. As shown in FIG. 14, transformer 1307 uses 16 adders, a imagery j multiplier and four real multipliers to implement equations (9a)-(9d), (22a) and (22d). The structure is different from an 8-IFFT. The four real multipliers are for the multiplication of real number 2, which can be simply implemented as a shift operation. As a result, transformer 1307 does not require any multipliers.
It can be seen from equations (12)-(18) and (24a)-(24f) that transformer 1307 only needs to form N/8-length sub-sequences {z1[n], z3[n], z5[n], z7[n]}and {w2[n], w4[n], w2[((n+N/8))N], w4[((n+N/8))N]}, n=0, . . . , (N/8)−1. As the eight subblocks {x[n], n=0, . . . , (N/8)−1}, {x[n], n=N/8, . . . , (2N/8)−1}, . . . , {x[n], n=7N/8, . . . , N−1} are no longer needed, the eight memory blocks having N/8 units each in memory 1005 can be released to store {z1[n], z3[n], z5[n], z7[n]}and {w2[n], w4[n], w2[((n+N/8))N], w4[((n+N/8))N]}, n=0, . . . , (N/8)−1. In other words, the required memory is 8×(N/8)=N units. Finally substituting equations (12)-(18) and (24a)-(24f) into equations (21) and (23), the following two results can be obtained:

    Result 1: p=0, 2, 4, 6, n=0, . . . , (N/8)−1






  
    
      
        
          
            
              
                
                  
                    x
                    ~
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              pN
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                ⁢
                
                  
                    
                      
                        b
                        ~
                      
                      1
                    
                    ⁢
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      5
                    
                    ⁢
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      3
                    
                    ⁢
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      7
                    
                    ⁢
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                
              
            
          
          
            
              
                
                ⁢
                
                  
                    
                      
                        b
                        ~
                      
                      2
                    
                    ⁢
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      4
                    
                    ⁢
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      6
                    
                    ⁢
                    
                      
                        w
                        4
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      8
                    
                    ⁢
                    
                      
                        w
                        4
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                
              
            
          
        
         
      
    
    
      
        (25a)
      
    
  




where the phase rotation parameter {tilde over (b)}l is shown in FIG. 15(a).

    Result 2: p=1, 3, 5, 7, n=0, . . . , (N/8)−1






  
    
      
        
          
            
              
                
                  
                    x
                    ~
                  
                  ⁡
                  
                    [
                    
                      
                        (
                        
                          (
                          
                            n
                            +
                            
                              pN
                              8
                            
                          
                          )
                        
                        )
                      
                      N
                    
                    ]
                  
                
                =
                
                ⁢
                
                  
                    
                      
                        b
                        ~
                      
                      1
                    
                    ⁢
                    
                      
                        z
                        1
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      5
                    
                    ⁢
                    
                      
                        z
                        5
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      3
                    
                    ⁢
                    
                      
                        z
                        3
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      7
                    
                    ⁢
                    
                      
                        z
                        7
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                  
                  +
                
              
            
          
          
            
              
                
                ⁢
                
                  
                    
                      
                        b
                        ~
                      
                      2
                    
                    ⁢
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                +
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      4
                    
                    ⁢
                    
                      
                        w
                        2
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                +
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                  +
                
              
            
          
          
            
              
                
                ⁢
                
                  
                    
                      
                        b
                        ~
                      
                      6
                    
                    ⁢
                    
                      
                        w
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                +
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                  +
                  
                    
                      
                        b
                        ~
                      
                      8
                    
                    ⁢
                    
                      
                        w
                        4
                      
                      ⁡
                      
                        [
                        
                          
                            (
                            
                              (
                              
                                n
                                +
                                
                                  N
                                  8
                                
                              
                              )
                            
                            )
                          
                          N
                        
                        ]
                      
                    
                  
                
              
            
          
        
         
      
    
    
      
        (25b)
      
    
  




where the phase rotation parameter {tilde over (b)}l is shown in FIG. 15(b).
Refer to FIG. 13, after the phase rotation of the six sub-sequences {z1[n], z3[n], z5[n], z7[n]} and {w2[n], w4[n]}, n=0, . . . , (N/8)−1, adder 1011 adds to form an N/8-length transmitted signal {{tilde over (x)}[0], {tilde over (x)}[1], . . . , x[(N/8)−1]}. By using different phase rotation parameter {tilde over (b)}l, the six sub-sequences {z1[n], z3[n], z5[n], z7[n]} and {w2[((n+N/8))N], w4[((n+N/8))N]}, n=0, . . . , (N/8)−1, can be used to obtain the next transmitted signal {{tilde over (x)}[N/8], {tilde over (x)}[(N/8)+1], . . . , {tilde over (x)}[(2N/8)−1]}. By the same way, the entire N-point transmitted signal {tilde over (x)}[n] can be obtained.
As shown in FIG. 13 and FIG. 14, when {tilde over (b)}l is +1, −1, +j, or −j, the multiplications that the simplified embodiment of the present invention requires only come from N-IFFT 801. Therefore, the total amount of complex multiplications is (N/2)log2N, and the memory requirement is N units.
FIG. 16 shows the comparison of the amount of computation and the memory requirement of the preferred (FIG. 10) and simplified (FIG. 13) embodiments of the present invention and the other three PTS methods, for M=8 and N=64, 256, 1024, and 2048. As can be seen in FIG. 16, the amount of computation and the memory requirement increases rapidly as N increases for the original PTS method and the method disclosed by Kang, Kim and Joo. In comparison, the simplified embodiment of the present invention and the Samsung's method take the minimum number of multiplications (160, 896, 4608, 10240 multiplications, respectively) and require the minimum memory space (64, 256, 1024, 2048 units of memory, respectively). However, the PTS method of the present invention does not shorten the length of the OFDM signal, and therefore still keeps the features and the advantages of the original OFDM system.
In summary, the present invention uses the interleaved partitioning of the subblocks of the PTS method, and uses only an N-IFFT to provide a method and an apparatus for high-order PAPR reduction for OFDM signal. The simplified embodiment of the present invention only takes (N/2)log2N multiplications and requires only N units of memory space. Furthermore, the present invention keeps the features and the advantages of the original OFDM system.
Although the present invention has been described with reference to the preferred embodiments, it will be understood that the invention is not limited to the details described thereof. Various substitutions and modifications have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.

## Claims

1. A method for high-order peak-to-average power ration (PAPR) reduction for an OFDM signal, comprising:
(a) transforming a frequency domain signal X[k] of length N by an N-IFFT into a time domain signal x[n] of length N, where N is the number of useful data in an OFDM symbol, n=0, 1, . . . , N−1;
(b) partitioning said sequence x[n] of length N into M disjoint subblocks, M being a power of 2 and greater or equal to 8, and N/M being an integer greater than 1;
(c) transforming said subblocks into sub-sequences z1 [n], each having the length N/M, l=1, 2, . . . , M and n=0, 1, . . . , (N/M)−1; and
(d) each said sub-sequence z1[n] being processed using complex multiplication followed by phase rotation or directly using phase rotation, then addition to form a complete N-point transmitted signal {tilde over (x)}[n].

2. The method as claimed in claim 1, wherein said transformation in said step (c) is equivalent to an M-point inverse fast Fourier transform (IFFT).

3. The method as claimed in claim 1, wherein said M is equal to 8.

4. The method as claimed in claim 1, wherein said transformation in said step (c) further comprises addition, imagery multiplication or complex multiplication.

5. The method as claimed in claim 1, wherein said complex multiplication in said step (d) is ej(2π/M).

6. The method as claimed in claim 1, wherein said method requires less than or equal to (N/2)log2N+(3N/4) complex multiplications.

7. The method as claimed in claim 1, wherein said step (d) further comprises the steps of:
(d1) a part of said M sub-sequences z1[n] being processed using complex multiplication ej(2π/M) to form another sub-sequence {tilde over (z)}l[n], l being between 1 and M, and n=0, 1, . . . , (N/M)−1; and
(d2) using different time period to select sub-sequence z1[n] or {tilde over (z)}l[n] for phase rotation, and adding to form a complete N-point transmitted signal {tilde over (x)}[n].

8. The method as claimed in claim 1, wherein in said step (d), said phase rotation parameter is of the four possibilities {+1, −1, +j, −j}.

9. An apparatus for PAPR reduction of an OFDM signal, comprising:
an N-point inverse fast Fourier transform (N-IFFT) for transforming N-length frequency domain signal X[k] into N-length time domain signal x[n], where N is the number of useful data in an OFDM symbol, n=0, 1, . . . , N−1;
a de-multiplexer for partitioning said time domain signal x[n] of length N into M disjoint subblocks of identical length N/M, where n=0, 1, . . . , N−1, N is an integer greater than 1, M is a power of 2 and greater than or equal to 8, and N/M is an integer greater than 1;
a transformer transforming said M disjoint subblocks into M N/M-length sub-sequences z[n], where l=1, 2, . . . , M and n=0, 1, . . . , (N/M)−1, for further complex multiplication or phase rotation;
at most M complex multipliers executing said complex multiplication on a part of said sub-sequences z1[n] to form another sub-sequence {tilde over (z)}l[n], where l is between 1 and M, and n=0, 1, . . . , (N/M)−1;
two sets of memories, one said memory storing said M disjoint subblocks and said M sub-sequences z1[n], and the other said memory storing said sub-sequences z1[n]; and
an adder for adding said sub-sequences z1[n] and {tilde over (z)}l[n], after phase rotation, to obtain a complete N-point transmitted signal {tilde over (x)}[n].

10. The apparatus as claimed in claim 9, wherein said M is 8, and said transformer is implemented with 24 adders, 3 imagery j multipliers and 2 complex multipliers.

11. The apparatus as claimed in claim 9, wherein said M is 8, and said transformer is implemented with 16 adders, 1 imagery j multipliers and 4 real multipliers.

12. The apparatus as claimed in claim 9, wherein said apparatus only uses an N-point inverse fast Fourier transform (N-IFFT).

13. The apparatus as claimed in claim 9, wherein said two sets of memories require less than or equal to 3N/2 units of memory.