Class: Array

Inherits:
Object
  • Object
show all
Defined in:
lib/fwt.rb

Overview

Implementation of Fast Walsh Transforms (FWTs) using sequency and Hadamard in-place transforms. Both algorithms are O(n log(n)).

Note that these transforms are their own inverse, to within a scale factor of array.length, because the transform matrix is orthogonal and symmetric about its diagonal.

Instance Method Summary collapse

Instance Method Details

#hadamard ⇒ Object

Perform a fast Walsh transformation using a Hadamard (natural) ordered in-place algorithm. The array is modified by this algorithm.



49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/fwt.rb', line 49

def hadamard
  raise "#{self.class}.#{__method__}: array length must be a power of 2" \
    unless length.power_of_2?
  lag = 1
  while lag < length
    offset = lag << 1
    ngroups = length / offset
    ngroups.times do |group|
      lag.times do |base|
        j = base + group * offset
        k = j + lag
        self[j], self[k] = self[j] + self[k], self[j] - self[k]
      end
    end
    lag = offset
  end
  self
end

#sequency ⇒ Object

Perform a fast Walsh transformation using a Manz sequency ordered in-place algorithm. The array is modified by this algorithm.



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/fwt.rb', line 14

def sequency
  raise "#{self.class}.#{__method__}: array length must be a power of 2" \
    unless length.power_of_2?
  j = 0
  0.upto(length - 3) do |i|  # Bit reversal sorting
    self[i], self[j] = self[j], self[i] if (i < j)
    k = length >> 1
    while (k <= j) do
      j -= k
      k >>= 1
    end
    j += k
  end
  offset = length
  while(offset > 1) do
    lag = offset >> 1
    ngroups = length / offset
    ngroups.times do |group|
      lag.times do |i|
        j = i + group * offset
        k = j + lag
        if (group.odd?)
          self[j], self[k] = self[j] - self[k], self[j] + self[k]
        else
          self[j], self[k] = self[j] + self[k], self[j] - self[k]
        end
      end
    end
    offset = lag
  end
  self
end