0
回答
自己写的H序walsh快速变换代码,需要的同学帮忙测试一下
注册华为云得mate10,2.9折抢先购!>>>   

自己写的H序walsh快速变换代码,需要的同学帮忙测试一下

算法见王能超的<<算法演化论>>P264-268

import java.util.Arrays;


public class walsh {

 /**
  * @param args
  */
 public static void main(String[] args) 
 {
  // TODO Auto-generated method stub
  int N = 16;
  
  int[][] x = new int[2][N] ;
  

  for( int i = 0 ; i < N ; ++i )
  {
   x[0][i] = i ;
   x[1][i] = 0 ;
  }
  
  System.out.println(Arrays.toString( fht(N,x) ));


 }
 
 //快速H序walsh变换
 //length表示变换的规模,必须是2的n次方幂
 //x是两行length列的二维数组,用来表示循环队列。
 //初始值存入x[0]
 
 
 public static int[]   fht( int length , int[][] x )
 {
 
  // 变量xu表示展开的层次,目的是为了确定变换前的数值和变换后的数值
  
  int xu = 0 ;

  /* 以下部分是当长度为8时,后述循环的展开,显示8-4-2两分过程  
  ht( 8,0,xu,x );
  
  xu++;
  
  ht( 4,0,xu,x );
  ht( 4,4,xu,x );
  
  xu++;
  
  
  ht( 2,0,xu,x );
  ht( 2,2,xu,x );
  
  ht( 2,4,xu,x );
  ht( 2,6,xu,x );
  
  
  */
  
  for( int j = 1 ; j < ( log2(length) + 1 )  ; ++j )
  {
   int p2j1 = pow2(j-1) ;
   
   int n = length / p2j1 ;
   
   int[] p = new int[ p2j1 ];
   
   for( int q = 0 ; q < p2j1 ; ++q )
   {
    p[q] = 0 + q * n;
   }
   
   for( int m = 0 ; m < p2j1; ++m   )
   {
    ht( n ,p[m] , xu , x );
   }
   
   xu++;
   
  }
  
  int xi = xu % 2;
  
  int [] y = new int[length];
  
  System.arraycopy(x[xi], 0, y, 0, length);

  return y;
  

 }

 
 //n规模H序walsh变换
 //n表示规模,8-4-2种的8,4,2
 //p表示本次变换操作的数值开始下标
 //例如8-ht转化成两个4-ht,第一个4-ht操作0,1,2,3四个数,开始下标0
 //第二个4-ht操作4,5,6,7四个数,开始下标4
 
 public static void ht(int n ,int p , int xu , int[][] x )
 {
  // xi yi 分别指示循环队列中的变换前值和变换后值
  
  int xi = xu % 2;
  int yi = (xi + 1) % 2;
  
  int m = n / 2 ;
  
  for( int j = 0 ; j < m ; ++j )
  {

   x[yi][ p + j ] = x[xi][ p + j ] + x[xi][ p + j + m ];
   
   
   x[yi][ p + j + m ] = x[xi][ p + j ] - x[xi][ p + j + m ];
   
  }
  
  //System.out.println(Arrays.toString(x[xi]));
  //System.out.println(Arrays.toString(x[yi]));
  
 }
 
 
 public static int log2( int m )
 {
  return (int)Math.round( (Math.log10(m)/Math.log10(2)) );
 }

 
 public static int pow2( int m )
 {

  return  (int) (Math.round(  Math.pow(2, m)  )) ;
  
 }
}

举报
草鞋
发帖于7年前 0回/265阅
顶部