signalGenerated

Generated from the source

Data comes from entelechy serve + {"op":"kernels"} / {"op":"kernel"} · packages/signal.entpkg/kernels/*.ent.

Category: Packages · Manifest: use "kernels/";

Brief

Fast Fourier transforms of complex numbers in rows 1 << bits long (at most 256), each row a group of lanes running every round of butterflies in place.

Description

Fast Fourier transforms of complex numbers in rows 1 << bits long (at most 256), each row a group of lanes running every round of butterflies in place: rows laid end to end, each transformed alone (blocks of a sound, lines of a picture), or a cube 1 << bits a side, x fastest, one axis a pass. The inverse divides by the row’s length, so one undoes the other.

Layer: Foundation. Uses: no other package.

use "signal.entpkg";

Kernels

• kernels/fourier.ent — Fast Fourier transforms of complex numbers (Vec2, real then imaginary) in rows n = 1 << bits long: rows laid end to end, or the rows of a cube n a side, element x + n * (y + n * z), along an axis. Kernels: signal.fourier_turns@1, signal.fourier_complex@1, signal.fourier_real@1, signal.fourier_rows@2.

Graph presets

• graphs/fourier_forward.esn — A cube’s transform, along z, then y, then x, 1 << bits a side (at most 256), laid as it came.
• graphs/fourier_inverse.esn — A spectrum’s cube again, along z, then y, then x, each axis divided by n, so it undoes fourier_forward.esn.
• graphs/fourier_rows_forward.esn — Rows of 1 << bits complex numbers laid end to end (at most 256 long), each transformed alone, laid as they came.
• graphs/fourier_rows_inverse.esn — Rows of spectra laid end to end again, each divided by its length, so it undoes fourier_rows_forward.esn.

Tests

tests/ holds scenes and their replays, run on every backend: fourier.replay. Every Kernel of the package is reached by one of them.

Kernels

Kernel	Mode	Brief
signal.fourier_complex@1	map	A real cube as complex numbers, the imaginary parts zero.
signal.fourier_real@1	map	The real parts of a complex cube.
signal.fourier_rows@2	group	Rows of n = 1 << bits (at most 256) transformed: element k + n * r of the result is wave number k of row r. The rows lie end to end, row r’s samples from r * n on; interleaved, they lie a row’s count apart, row r’s sample j at r + j * count / n, which is a cube n a side along its slowest axis: the axis transformed comes out fastest and the other two follow in order, so three passes transform the cube along every axis and leave it laid as it came. A group holds 256 / n whole rows: each lane reads its row’s sample in bit-reversed order, then bits rounds of butterflies (radix 2, Cooley and Tukey), each lane swapping with the lane 1 << round away and the odd one turned by e^(sign 2 pi i r / width), sign -1 forward; scaled, divided by n. A lane past the input’s end reads zero.
signal.fourier_turns@1	map	The turns a transform 1 << bits long multiplies by: (cos, sin) of 2 pi k / n; a node sets domain = 1 << bits.

Methods

Function	Brief
cmul(a: Vec2, b: Vec2) -> Vec2	The product of two complex numbers.
cube_cell(e: Int, n: Int) -> IVec3	The cell of element e in a cube n a side.
cube_index(c: IVec3, n: Int) -> Int	The element of cell c, wrapped round the cube’s sides.
wave_number(i: Int, n: Int) -> Int	The signed wave number of index i along a side n long: 0 to n / 2 - 1, then -n / 2 to -1.
reversed_bits(i: Int, bits: Int) -> Int	i’s lowest bits bits in the other order.

Graph presets

Name	Interface	Description
fourier_forward	input data: Rows<Vec2> param bits: Int = 6 output result <- x.result	A cube’s transform, along z, then y, then x, 1 << bits a side (at most 256), laid as it came: node spectrum: graph “signal.entpkg/graphs/fourier_forward.esn” { data <- cube.result; bits = 7; }
fourier_inverse	input data: Rows<Vec2> param bits: Int = 6 output result <- x.result	A spectrum’s cube again, along z, then y, then x, each axis divided by n, so it undoes fourier_forward.esn: node cube: graph “signal.entpkg/graphs/fourier_inverse.esn” { data <- spectrum.result; bits = 7; }
fourier_rows_forward	input data: Rows<Vec2> param bits: Int = 6 output result <- rows.result	Rows of 1 << bits complex numbers laid end to end (at most 256 long), each transformed alone, laid as they came: node spectra: graph “signal.entpkg/graphs/fourier_rows_forward.esn” { data <- blocks.result; bits = 8; }
fourier_rows_inverse	input data: Rows<Vec2> param bits: Int = 6 output result <- rows.result	Rows of spectra laid end to end again, each divided by its length, so it undoes fourier_rows_forward.esn: node blocks: graph “signal.entpkg/graphs/fourier_rows_inverse.esn” { data <- spectra.result; bits = 8; }

Kernel descriptions

signal.fourier_complex@1

A real cube as complex numbers, the imaginary parts zero.

Mode	map
Requires	field.read, field.write
Inputs	real: Rows<Float>
Params	—
Outputs	result: Rows<Vec2>
Source	packages/signal.entpkg/kernels/fourier.ent

signal.fourier_real@1

The real parts of a complex cube.

Mode	map
Requires	field.read, field.write
Inputs	data: Rows<Vec2>
Params	—
Outputs	result: Rows<Float>
Source	packages/signal.entpkg/kernels/fourier.ent

signal.fourier_rows@2

Rows of n = 1 << bits (at most 256) transformed: element k + n * r of the result is wave number k of row r. The rows lie end to end, row r’s samples from r * n on; interleaved, they lie a row’s count apart, row r’s sample j at r + j * count / n, which is a cube n a side along its slowest axis: the axis transformed comes out fastest and the other two follow in order, so three passes transform the cube along every axis and leave it laid as it came. A group holds 256 / n whole rows: each lane reads its row’s sample in bit-reversed order, then bits rounds of butterflies (radix 2, Cooley and Tukey), each lane swapping with the lane 1 << round away and the odd one turned by e^(sign 2 pi i r / width), sign -1 forward; scaled, divided by n. A lane past the input’s end reads zero.

Mode	group
Requires	field.read, field.write
Inputs	data: Rows<Vec2>, turns: Rows<Vec2>
Params	bits: Int = 6, interleaved: Bool = False, sign: Float = -1.0, scaled: Bool = False
Outputs	result: Rows<Vec2>
Source	packages/signal.entpkg/kernels/fourier.ent

signal.fourier_turns@1

The turns a transform 1 << bits long multiplies by: (cos, sin) of 2 pi k / n; a node sets domain = 1 << bits.

Mode	map
Requires	field.write
Inputs	—
Params	bits: Int = 6
Outputs	result: Rows<Vec2>
Source	packages/signal.entpkg/kernels/fourier.ent

Tests

fourier.replay