2b:null 2c:["$","title",null,{"children":"Explorable DFT | Jasmine Otto | Observable"}] 31:T5a3,viewof coeffs = { let node = DOM.svg(w, h), svg = d3.select(node) svg.style('overflow', 'visible') let ret = dft(samples.map(d => d.v)) // coefficients depend on the sampled signal ret.forEach((c,k) => c.index = k) // annotate each coefficient by its frequency let y = yFreq, x = xFreq let bind = function(d,i) { // redraw & broadcast when a coefficient is dragged let [xIn,yIn] = d3.mouse(this) let j = ret.length - i if (i != 0 && i != j) { ret[i].re = x.invert(xIn) ret[i].im = y.invert(yIn) ret[j].re = ret[i].re ret[j].im = -ret[i].im } else { ret[i].re = x.invert(xIn) } svg.selectAll('circle.coeff') .attr('cx', (d) => x(d.re)) .attr('cy', (d) => y(d.im)) node.dispatchEvent(new CustomEvent('input')) } let r = (mag) => xFreq(mag - .5) // BRITTLE svg.selectAll('circle') .data([ .5, .3, .2, .1 ]).join('circle') .attr('cx', x(0)).attr('cy', y(0)) .attr('r', d => r(d) ) .style('fill', 'none').style('stroke', 'lightgray') svg.selectAll('circle.coeff') .data(ret).join('circle') .attr('class', 'coeff') .attr('cx', (d) => x(d.re)) .attr('cy', (d) => y(d.im)) .attr('r', 5) .style('fill', 'white') .style('stroke', (_,i) => blues[i]) .style('stroke-width', 3) .call(d3.drag().on('drag', bind)) node.value = ret return node }32:T641,ift = /** * Inverse Discrete Fourier Transform (IDFT): frequencies to time. * * Time complexity: O(N^2) * * @param {ComplexNumber[]} frequencies - Frequencies summands of the final signal. * @param {number} zeroThreshold - Threshold that is used to convert real and imaginary numbers * to zero in case if they are smaller then this. * * @return {number[]} - Discrete amplitudes distributed in time. */ function ( frequencies, zeroThreshold = CLOSE_TO_ZERO_THRESHOLD, ) { const N = frequencies.length; const amplitudes = []; // Go through every discrete point of time. for (let timer = 0; timer < N; timer += 1) { // Compound amplitude at current time. let amplitude = new ComplexNumber(); // Go through all discrete frequencies. for (let frequency = 0; frequency < N; frequency += 1) { const currentFrequency = frequencies[frequency]; // Calculate rotation angle. const rotationAngle = (2 * Math.PI) * frequency * (timer / N); // Remember that e^ix = cos(x) + i * sin(x); const frequencyContribution = new ComplexNumber({ re: Math.cos(rotationAngle), im: Math.sin(rotationAngle), }).multiply(currentFrequency); amplitude = amplitude.add(frequencyContribution); } // Close to zero? You're zero. if (Math.abs(amplitude.re) < zeroThreshold) { amplitude.re = 0; } if (Math.abs(amplitude.im) < zeroThreshold) { amplitude.im = 0; } // Add current frequency signal to the list of compound signals. amplitudes[timer] = amplitude.re; } return amplitudes; }33:T9d5,/** * Discrete Fourier Transform (DFT): time to frequencies. * * Time complexity: O(N^2) * * @param {number[]} inputAmplitudes - Input signal amplitudes over time (complex * numbers with real parts only). * @param {number} zeroThreshold - Threshold that is used to convert real and imaginary numbers * to zero in case if they are smaller then this. * * @return {ComplexNumber[]} - Array of complex number. Each of the number represents the frequency * or signal. All signals together will form input signal over discrete time periods. Each signal's * complex number has radius (amplitude) and phase (angle) in polar form that describes the signal. * * @see https://gist.github.com/anonymous/129d477ddb1c8025c9ac * @see https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/ */ function dft(inputAmplitudes, zeroThreshold = CLOSE_TO_ZERO_THRESHOLD) { const N = inputAmplitudes.length; const signals = []; // Go through every discrete frequency. for (let frequency = 0; frequency < N; frequency += 1) { // Compound signal at current frequency that will ultimately // take part in forming input amplitudes. let frequencySignal = new ComplexNumber(); // Go through every discrete point in time. for (let timer = 0; timer < N; timer += 1) { const currentAmplitude = inputAmplitudes[timer]; // Calculate rotation angle. const rotationAngle = -1 * (2 * Math.PI) * frequency * (timer / N); // Remember that e^ix = cos(x) + i * sin(x); const dataPointContribution = new ComplexNumber({ re: Math.cos(rotationAngle), im: Math.sin(rotationAngle), }).multiply(currentAmplitude); // Add this data point's contribution. frequencySignal = frequencySignal.add(dataPointContribution); } // Close to zero? You're zero. if (Math.abs(frequencySignal.re) < zeroThreshold) { frequencySignal.re = 0; } if (Math.abs(frequencySignal.im) < zeroThreshold) { frequencySignal.im = 0; } // Average contribution at this frequency. // The 1/N factor is usually moved to the reverse transform (going from frequencies // back to time). This is allowed, though it would be nice to have 1/N in the forward // transform since it gives the actual sizes for the time spikes. frequencySignal = frequencySignal.divide(N); // Add current frequency signal to the list of compound signals. signals[frequency] = frequencySignal; } return signals; }34:Tf85,class ComplexNumber { /** * z = re + im * i * z = radius * e^(i * phase) * * @param {number} [re] * @param {number} [im] */ constructor({ re = 0, im = 0 } = {}) { this.re = re; this.im = im; } /** * @param {ComplexNumber|number} addend * @return {ComplexNumber} */ add(addend) { // Make sure we're dealing with complex number. const complexAddend = this.toComplexNumber(addend); return new ComplexNumber({ re: this.re + complexAddend.re, im: this.im + complexAddend.im, }); } /** * @param {ComplexNumber|number} subtrahend * @return {ComplexNumber} */ subtract(subtrahend) { // Make sure we're dealing with complex number. const complexSubtrahend = this.toComplexNumber(subtrahend); return new ComplexNumber({ re: this.re - complexSubtrahend.re, im: this.im - complexSubtrahend.im, }); } /** * @param {ComplexNumber|number} multiplicand * @return {ComplexNumber} */ multiply(multiplicand) { // Make sure we're dealing with complex number. const complexMultiplicand = this.toComplexNumber(multiplicand); return new ComplexNumber({ re: this.re * complexMultiplicand.re - this.im * complexMultiplicand.im, im: this.re * complexMultiplicand.im + this.im * complexMultiplicand.re, }); } /** * @param {ComplexNumber|number} divider * @return {ComplexNumber} */ divide(divider) { // Make sure we're dealing with complex number. const complexDivider = this.toComplexNumber(divider); // Get divider conjugate. const dividerConjugate = this.conjugate(complexDivider); // Multiply dividend by divider's conjugate. const finalDivident = this.multiply(dividerConjugate); // Calculating final divider using formula (a + bi)(a − bi) = a^2 + b^2 const finalDivider = (complexDivider.re ** 2) + (complexDivider.im ** 2); return new ComplexNumber({ re: finalDivident.re / finalDivider, im: finalDivident.im / finalDivider, }); } /** * @param {ComplexNumber|number} number */ conjugate(number) { // Make sure we're dealing with complex number. const complexNumber = this.toComplexNumber(number); return new ComplexNumber({ re: complexNumber.re, im: -1 * complexNumber.im, }); } /** * @return {number} */ getRadius() { return Math.sqrt((this.re ** 2) + (this.im ** 2)); } /** * @param {boolean} [inRadians] * @return {number} */ getPhase(/*inRadians = true*/) { let phase = Math.atan(Math.abs(this.im) / Math.abs(this.re)); if (this.re < 0 && this.im > 0) { phase = Math.PI - phase; } else if (this.re < 0 && this.im < 0) { phase = -(Math.PI - phase); } else if (this.re > 0 && this.im < 0) { phase = -phase; } else if (this.re === 0 && this.im > 0) { phase = Math.PI / 2; } else if (this.re === 0 && this.im < 0) { phase = -Math.PI / 2; } else if (this.re < 0 && this.im === 0) { phase = Math.PI; } else if (this.re > 0 && this.im === 0) { phase = 0; } else if (this.re === 0 && this.im === 0) { // More correctly would be to set 'indeterminate'. // But just for simplicity reasons let's set zero. phase = 0; } /* if (!inRadians) { phase = radianToDegree(phase); } */ return phase; } /** * @param {boolean} [inRadians] * @return {{radius: number, phase: number}} */ getPolarForm(inRadians = true) { return { radius: this.getRadius(), phase: this.getPhase(inRadians), }; } /** * Convert real numbers to complex number. * In case if complex number is provided then lefts it as is. * * @param {ComplexNumber|number} number * @return {ComplexNumber} */ toComplexNumber(number) { if (number instanceof ComplexNumber) { return number; } return new ComplexNumber({ re: number }); } }35:[] 2f:{"id":"d682dd9d0982fb9e","slug":"explorable-dft","title":"Explorable DFT","thumbnail":"14d66d261974ebeec3cd9214ca42087cb7d8fee08a171053a182b63c61ddd534","access_level":"public","create_time":"$D2019-07-15T18:10:05.160Z","update_time":"$D2026-05-14T22:55:07.392Z","view_time":null,"first_public_time":"$D2019-07-23T21:18:09.104Z","fork":true,"stars":7,"starred":false,"owner":{"type":"team","id":"43e035ce64fad801","login":"jazztap","name":"Jasmine Otto","avatar_url":"https://avatars-next.observableusercontent.com/1d847b962089e3524d821a011682b5ec09925cb269ab3f15456fb6e38e574bcc","tier":"starter_2024"},"version":1373,"publish_version":1373,"role":null,"authored":false,"authors":[{"type":"individual","id":"91a3f7bf83a60ddd","login":"jazztap","name":"Jasmine Otto","avatar_url":"https://avatars-next.observableusercontent.com/1d847b962089e3524d821a011682b5ec09925cb269ab3f15456fb6e38e574bcc","tier":null}],"members":[{"type":"individual","id":"91a3f7bf83a60ddd","login":"jazztap","name":"Jasmine Otto","avatar_url":"https://avatars-next.observableusercontent.com/1d847b962089e3524d821a011682b5ec09925cb269ab3f15456fb6e38e574bcc","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"Explorable DFT","cells":[{"id":15,"value":"md`# Explorable DFT`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":753,"value":"md`\n**Libraries:** \n[JavaScript Algorithms and Data Structures](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fourier-transform) for the discrete Fourier transform, its inverse, and a corresponding ComplexNumber class. \n[vegalite](https://observablehq.com/@mbostock/exploring-data-with-vega-lite) for plotting. \nd3 for interaction.\n\nCharts on the right-hand side are interactive at each node. \nDocs forthcoming.\n\n| ||Left|Right|\n|-|-|-|-|\n|**Above** | |Sum of frequency components i.e. the reconstructed time series.| Time series of real-valued samples.|\n|**Below** | |Time series of each frequency component. | Frequency coefficients, in the complex plane.|\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1073,"value":"nth = (i) => `${i}${i <= 3 ? ['th', 'st', 'nd', 'rd'][i] : 'th'}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":69,"value":"N = 6","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":509,"value":"initSignal = () => {\n let ret = Array(N).fill()\n ret.forEach((_,i,arr) => {\n ret[i] = {v: i > 0 ? arr[i-1].v + 2*(Math.random() - .5) : 0} \n // Math.abs(Math.sin(i*TWO_PI /N))\n // [.5,0,.5,1,.5,0,.5]\n })\n return ret\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":132,"value":"unit_with_angle = (theta) => new ComplexNumber({re: Math.cos(theta), im: Math.sin(theta)})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":53,"value":"// sample the frequency-encoded signal at time 'n'\nsample = (n, eps = CLOSE_TO_ZERO_THRESHOLD) => {\n let ret = sample_raw(n).reduce((a,b) => a.add(b), new ComplexNumber(0))\n ret.re = Math.abs(ret.re) < eps ? 0 : ret.re\n ret.im = Math.abs(ret.im) < eps ? 0 : ret.im\n return ret\n}\n\n/* sample = (freqs, n, eps = CLOSE_TO_ZERO_THRESHOLD) => {\n \n let ret = freqs.map((c,i) => c.multiply(exp(i*n) // weight the ith value by the complex coefficient\n )).reduce((a,b) => a + b.re, 0) // take the sum (discarding imaginary part)\n return Math.abs(ret) < eps ? 0 : ret\n } */","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":674,"value":"sample_raw = (n) => // returns the contribution of each complex coefficient at the sample point 'n'\n coeffs.map((c,k) => k < LOW_PASS ?\n c.multiply( unit_with_angle(k*n * TWO_PI/N) )\n : new ComplexNumber() )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":396,"value":"dashboard =\nhtml`

\n ${time_value} ${viewof samples}\n ${amplitude_time} ${viewof coeffs}\n

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1026,"value":"viewof LOW_PASS = html` 10 ? N/2 : N} />`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1066,"value":"md`Filter out frequency coefficients beyond the ${nth(LOW_PASS-1)}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":903,"value":"w = 1.5*h","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":904,"value":"h = 225","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1370,"value":"// WIP: trace of the frequency-space representation in complex space, marked at sample points.\n\n// FIXME: 'low-pass filter' is clobbering all the conjugate pairs","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1294,"value":"vegalite({\n height: h,\n layer: [{\n data: {\n values: d3.range(N*LERP).map(k => ({...sample(k/LERP), idx: k}) )\n },\n mark: {\n type: \"line\",\n interpolate: \"cardinal-closed\"\n },\n encoding: {\n x: {field: \"im\", type: \"quantitative\", scale: {domain: [-1, 1]}},\n y: {field: \"re\", type: \"quantitative\", scale: {domain: [-1, 1]}},\n order: {field: 'idx', type: \"quantitative\"}\n }\n },\n {\n data: {values: d3.range(N).map(k => sample(k)) },\n mark: 'point',\n encoding: {\n x: {field: \"im\", type: \"quantitative\"},\n y: {field: \"re\", type: \"quantitative\"},\n }\n },\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":455,"value":"yTime = d3.scaleLinear().domain([-2,2]).range([h,0])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":865,"value":"xTime = (i) => Math.floor((i+1) * w / (N+1))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":462,"value":"yFreq = d3.scaleLinear().domain([-.5,.5]).range([h,0])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":819,"value":"xFreq = d3.scaleLinear().domain([-.5,1]).range([0,w])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":872,"value":"lerpArgLinear = d3.line().x((_,i) => xTime(i)).y(d => yTime(d.v))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":515,"value":"setArg( ift(coeffs) ) // bind samples to coefficients\n// vega-lite charts also depend on coeffs, via sample_raw","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":453,"value":"setArg = (arg_) => {\n samples.forEach((d,i) => {d.v = arg_[i]} )\n\n // redraw samples (do not rebroadcast)\n d3.select(viewof samples).selectAll('circle')\n .attr('cy', (d) => yTime(d.v)) \n d3.select(viewof samples).select('path').attr('d', lerpArgLinear(samples))\n return arg_\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":847,"value":"blues = 2 < N && N < 10 ? d3.schemeBlues[N] :\n d3.range(N).map(i => d3.interpolateBlues(i/N));","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1352,"value":"md`#### inputs`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":308,"value":"viewof samples = {\n let node = DOM.svg(w, h),\n svg = d3.select(node)\n svg.style('overflow', 'visible')\n \n let y = yTime\n let ret = initSignal()\n let x = xTime\n \n let line = lerpArgLinear\n \n let bind = function(d,i) { // redraw & broadcast when a sample point is dragged\n let [_,yIn] = d3.mouse(this)\n ret[i].v = y.invert(yIn)\n \n svg.selectAll('circle')\n .attr('cy', (d) => y(d.v))\n svg.select('path').attr('d', line(ret))\n node.dispatchEvent(new CustomEvent('input'))\n }\n \n svg.append('path')\n .attr('d', line(ret))\n .style('fill', 'none').style('stroke', blues[N-1])\n .style('stroke-width', 3)\n \n svg.selectAll('circle')\n .data(ret).join('circle')\n .attr('cx', (_,i) => x(i)) // constant\n .attr('cy', (d) => y(d.v))\n .attr('r', 10)\n .style('fill', blues[N-2])\n .call(d3.drag().on('drag', bind))\n \n node.value = ret\n return node\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":423,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1354,"value":"md`#### outputs`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":708,"value":"LERP = 10","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":199,"value":"time_value = vegalite({\n height: h,\n layer: [\n {\n data: {values: Array(N*LERP).fill().map((_,i) => ({\n time: i/LERP,\n value: sample(i/LERP).re //* N\n }) )},\n mark: {\n type: \"line\",\n // interpolate: \"cardinal\",\n },\n encoding: {\n x: {field: \"time\", type: \"quantitative\"},\n y: {field: \"value\", type: \"quantitative\"},\n }\n },\n {\n data: {values: samples.map((d,i) => ({time: i, value: d.v}) )},\n mark: 'point',\n encoding: {\n x: {field: \"time\", type: \"quantitative\"},\n y: {field: \"value\", type: \"quantitative\"},\n }\n },\n ]\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":703,"value":"values = Array(N*LERP).fill().map((_,i) => {\n let res = sample_raw(i/LERP)\n return Array(N).fill().map((_,j) => ({\n time: i/LERP,\n amplitude: res[j].re,\n frequency: j\n }))\n }).flat()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":130,"value":"amplitude_time = vegalite({\n height: h,\n data: {\n values: values\n },\n mark: {\n type: \"line\",\n interpolate: \"cardinal\"\n },\n encoding: {\n x: {field: \"time\", type: \"quantitative\"},\n y: {field: \"amplitude\", type: \"quantitative\"},\n color: {field: \"frequency\", type: \"quantitative\", legend: null}\n }\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":32,"value":"fourier_coeffs = vegalite({\n data: {\n values: coeffs\n },\n mark: \"point\",\n encoding: {\n x: {field: \"re\", type: \"quantitative\", scale: {domain: [-.5, .5]}},\n y: {field: \"im\", type: \"quantitative\", scale: {domain: [-.5, .5]}},\n color: {field: \"index\", type: \"quantitative\"}\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":303,"value":"d3 = require('d3@v5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":661,"value":"// embed = require('vega-embed@4')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":26,"value":"vegalite = require('@observablehq/vega-lite@0.1')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":406,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1141,"value":"TWO_PI = Math.PI * 2","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1144,"value":"CLOSE_TO_ZERO_THRESHOLD = 1e-10;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":55,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 30:"$2f:body"