Wednesday, August 6, 2008

Lowest Common Mulitple of Periods within an Octave

In digital signal processing, it is sometimes required that one calculate the lowest common multiple of a number of periods. For example, imagine we have two sine waves with periods of 6 and 8 samples, and wish to calculate the discrete Fourier transform to determine the phase and amplitude of these two frequencies. Since the DFT assumes that the wave is periodic, we should use a DFT length of 24, the lowest common multiple of 6 and 8.

I came upon the inverse problem when designing a system to generate square waves, which would be analyzed with a DFT. However this problem had a further constraint, I needed to avoid interfering harmonics. A square wave has odd harmonics of the fundamental frequency. That is, for a 1 Hz square wave, there will be components at 3, 5, 7, ... Hz. In order to avoid interference between frequencies, I needed to find the shortest DFT length k that was a multiple of N periods, where the ratio of the largest and smallest periods was less than 3.

It took a bit of time to brute force the problem, so I'll include the results here:
N=3 k=12 p=[ 2 3 4 ]
N=4 k=60 p=[ 2 3 4 5 ]
N=5 k=120 p=[ 4 5 6 8 10 ]
N=6 k=240 p=[ 8 10 12 15 16 20 ]
N=7 k=360 p=[ 8 9 10 12 15 18 20 ]
N=8 k=720 p=[ 8 9 10 12 15 16 18 20 ]
N=9 k=840 p=[ 14 15 20 21 24 28 30 35 40 ]
N=10 k=1680 p=[ 14 15 16 20 21 24 28 30 35 40 ]
N=11 k=2520 p=[ 24 28 30 35 36 40 42 45 56 60 63 ]
N=12 k=2520 p=[ 24 28 30 35 36 40 42 45 56 60 63 70 ]
N=13 k=5040 p=[ 28 30 35 36 40 42 45 48 56 60 63 70 72 ]
N=14 k=5040 p=[ 28 30 35 36 40 42 45 48 56 60 63 70 72 80 ]
N=15 k=10080 p=[ 56 60 63 70 72 80 84 90 96 105 112 120 126 140 144 ]
N=16 k=10080 p=[ 56 60 63 70 72 80 84 90 96 105 112 120 126 140 144 160 ]
N=17 k=15120 p=[ 48 54 56 60 63 70 72 80 84 90 105 108 112 120 126 135 140 ]
N=18 k=25200 p=[ 60 63 70 72 75 80 84 90 100 105 112 120 126 140 144 150 168 175 ]
N=19 k=27720 p=[ 55 56 60 63 66 70 72 77 84 88 90 99 105 110 120 126 132 140 154 ]
N=20 k=30240 p=[ 96 105 108 112 120 126 135 140 144 160 168 180 189 210 216 224 240 252 270 280 ]
N=21 k=50400 p=[ 120 126 140 144 150 160 168 175 180 200 210 224 225 240 252 280 288 300 315 336 350 ]
N=22 k=55440 p=[ 60 63 66 70 72 77 80 84 88 90 99 105 110 112 120 126 132 140 144 154 165 168 ]
N=23 k=55440 p=[ 60 63 66 70 72 77 80 84 88 90 99 105 110 112 120 126 132 140 144 154 165 168 176 ]
N=24 k=83160 p=[ 105 108 110 120 126 132 135 140 154 165 168 180 189 198 210 216 220 231 252 264 270 280 297 308 ]
N=25 k=110880 p=[ 120 126 132 140 144 154 160 165 168 176 180 198 210 220 224 231 240 252 264 280 288 308 315 330 336 ]
N=26 k=110880 p=[ 120 126 132 140 144 154 160 165 168 176 180 198 210 220 224 231 240 252 264 280 288 308 315 330 336 352 ]
N=27 k=166320 p=[ 210 216 220 231 240 252 264 270 280 297 308 315 330 336 360 378 385 396 420 432 440 462 495 504 528 540 560 ]
N=28 k=166320 p=[ 210 216 220 231 240 252 264 270 280 297 308 315 330 336 360 378 385 396 420 432 440 462 495 504 528 540 560 594 ]
N=29 k=166320 p=[ 210 216 220 231 240 252 264 270 280 297 308 315 330 336 360 378 385 396 420 432 440 462 495 504 528 540 560 594 616 ]

Now, while the square wave has no even harmonics, these harmonics can be generated by non-linear processes, such as the saturation of vacuum tubes. So the same analysis was performed, constraining the ratio of the maximum and minimum periods to be less than 2 (or within one octave). Here are the results:
N=3 k=60 p=[ 3 4 5 ]
N=4 k=180 p=[ 9 10 12 15 ]
N=5 k=720 p=[ 8 9 10 12 15 ]
N=6 k=840 p=[ 20 21 24 28 30 35 ]
N=7 k=2520 p=[ 35 36 40 42 45 56 60 ]
N=8 k=2520 p=[ 35 36 40 42 45 56 60 63 ]
N=9 k=5040 p=[ 35 36 40 42 45 48 56 60 63 ]
N=10 k=10080 p=[ 56 60 63 70 72 80 84 90 96 105 ]
N=11 k=15120 p=[ 70 72 80 84 90 105 108 112 120 126 135 ]
N=12 k=27720 p=[ 55 56 60 63 66 70 72 77 84 88 90 99 ]
N=13 k=27720 p=[ 55 56 60 63 66 70 72 77 84 88 90 99 105 ]
N=14 k=55440 p=[ 55 56 60 63 66 70 72 77 80 84 88 90 99 105 ]
N=15 k=83160 p=[ 165 168 180 189 198 210 216 220 231 252 264 270 280 297 308 ]
N=16 k=83160 p=[ 165 168 180 189 198 210 216 220 231 252 264 270 280 297 308 315 ]
N=17 k=110880 p=[ 198 210 220 224 231 240 252 264 280 288 308 315 330 336 352 360 385 ]
N=18 k=166320 p=[ 165 168 176 180 189 198 210 216 220 231 240 252 264 270 280 297 308 315 ]
N=19 k=221760 p=[ 252 264 280 288 308 315 320 330 336 352 360 385 396 420 440 448 462 480 495 ]
N=20 k=277200 p=[ 264 275 280 300 308 315 330 336 350 360 385 396 400 420 440 450 462 495 504 525 ]
N=21 k=332640 p=[ 198 210 216 220 224 231 240 252 264 270 280 288 297 308 315 330 336 352 360 378 385 ]
N=22 k=360360 p=[ 252 260 264 273 280 286 308 312 315 330 360 364 385 390 396 420 429 440 455 462 468 495 ]
N=23 k=554400 p=[ 264 275 280 288 300 308 315 330 336 350 352 360 385 396 400 420 440 450 462 480 495 504 525 ]
N=24 k=720720 p=[ 504 520 528 546 560 572 585 616 624 630 660 693 715 720 728 770 780 792 819 840 858 880 910 924 ]
N=25 k=720720 p=[ 504 520 528 546 560 572 585 616 624 630 660 693 715 720 728 770 780 792 819 840 858 880 910 924 936 ]
N=26 k=720720 p=[ 504 520 528 546 560 572 585 616 624 630 660 693 715 720 728 770 780 792 819 840 858 880 910 924 936 990 ]
N=27 k=720720 p=[ 504 520 528 546 560 572 585 616 624 630 660 693 715 720 728 770 780 792 819 840 858 880 910 924 936 990 1001 ]

So, for example, the period of the shortest repeating waveform with 12 frequencies within an octave is 15120. If we allow frequencies up to the 2nd harmonic of the lowest frequency, the shortest period is 2520.

No comments: