Existence theorems for transforms over finite rings with applications to D convolution
Author:
David P. Maher
Journal:
Math. Comp. 35 (1980), 757765
MSC:
Primary 1004; Secondary 94B35
MathSciNet review:
572853
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: An existence theorem for Fourierlike transforms over arbitrary finite commutative rings is proven in a simple fashion. Corollaries for the case of residue class rings over the integers and extensions of those rings follow directly. The theory is applied to construct very fast algorithms for the computation of twodimensional convolutions over the integers .
 [1]
Ramesh
C. Agarwal and C.
Sidney Burrus, Number theoretic transforms to implement fast
digital convolution, Proc. IEEE 63 (1975),
no. 4, 550–560. MR 0451632
(56 #9914)
 [2]
Ramesh
C. Agarwal and Charles
S. Burrus, Fast convolution using Fermat number transforms with
applications to digital filtering, IEEE Trans. Acoust. Speech Signal
Processing ASSP22 (1974), no. 2, 87–97. MR 0398650
(53 #2501)
 [3]
Ramesh
C. Agarwal and Charles
S. Burrus, Fast onedimensional digital convolution by
multidimensional techniques, IEEE Trans. Acoust. Speech Signal
Processing ASSP22 (1974), no. 1, 1–10. MR 0401340
(53 #5169)
 [4]
R. C. AGARWAL & J. W. COOLEY, "New algorithms for digital convolution," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 392409.
 [5]
Rafael
C. Gonzalez and Paul
Wintz, Digital image processing, AddisonWesley Publishing
Co., Reading, Mass.LondonAmsterdam, 1977. Applied Mathematics and
Computation, No. 13. MR 0459042
(56 #17240)
 [6]
Jørn
Justesen, On the complexity of decoding ReedSolomon codes,
IEEE Trans. Information Theory IT22 (1976), no. 2,
237–238. MR 0465505
(57 #5404)
 [7]
D.
Kibler, Necessary and sufficient conditions for the existence of
the modular Fourier transform: Comments on “Number theoretic
transforms to implement fast digital convolution” (Proc. IEEE 63
(1975), no. 4, 550–560) by R. C. Agarwal and C. S. Burrus, Proc.
IEEE 65 (1977), no. 2, 265–267. With a reply by
the authors. MR
0490402 (58 #9748)
 [8]
Serge
Lang, Algebra, AddisonWesley Publishing Co., Inc., Reading,
Mass., 1965. MR
0197234 (33 #5416)
 [9]
David
P. Maher, Twodimensional digital filtering using transforms over
extensions of finite rings, Information linkage between applied
mathematics and industry, II (Proc. Second Annual Workshop, Monterey,
Calif., 1979) Academic Press, New YorkLondon, 1980,
pp. 269–278. MR 592274
(82a:94021)
 [10]
F. J. MacWILLIAMS &. N. J. A. SLOANE, The Theory of ErrorCorrecting Codes, NorthHolland, Amsterdam, 1977.
 [11]
Hideo
Murakami, Irving
S. Reed, and Lloyd
R. Welch, A transform decoder for ReedSolomon codes in
multipleuser communication systems, IEEE Trans. Information Theory
IT23 (1977), no. 6, 675–683. MR 0469496
(57 #9282)
 [12]
Peter
J. Nicholson, Algebraic theory of finite Fourier transforms,
J. Comput. System Sci. 5 (1971), 524–547. MR 0286905
(44 #4112)
 [13]
H. J. NUSSBAUMER, "Digital filtering using pseudo Fermat number transforms," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 7983.
 [14]
H.
J. Nussbaumer and P.
Quandalle, Computation of convolutions and discrete Fourier
transforms by polynomial transforms, IBM J. Res. Develop.
22 (1978), no. 2, 134–144. MR 0471260
(57 #10997)
 [15]
J.
M. Pollard, The fast Fourier transform in a finite
field, Math. Comp. 25 (1971), 365–374. MR 0301966
(46 #1120), http://dx.doi.org/10.1090/S00255718197103019660
 [16]
Charles
M. Rader, Discrete convolutions via Mersenne transforms, IEEE
Trans. Computers C21 (1972), 1269–1273. MR 0438672
(55 #11580)
 [17]
Irving
S. Reed and T.
K. Truong, Complex integer convolutions over a direct sum of Galois
fields, IEEE Trans. Information Theory IT21 (1975),
no. 6, 657–661. MR 0435049
(55 #8011)
 [18]
M. C. VANWORMHOUDT, "On number theoretic transforms in residue class rings," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 585586.
 [19]
E. VEGH & L. M. LIEBOWITZ, Fast Complex Convolution Using Number Theoretic Transforms, NRL Report 7935, Naval Research Lab., Washington, D.C., 1975, pp. 113.
 [20]
S.
Winograd, Some bilinear forms whose multiplicative complexity
depends on the field of constants, Math. Systems Theory
10 (1976/77), no. 2, 169–180. Sixteenth Annual
Symposium on Foundations of Computer Science (Berkeley, Calif., 1975),
selected papers. MR 0468322
(57 #8158)
 [1]
 R. C. AGARWAL & C. S. BURRUS, "Number theoretic transforms to implement fast digital convolutions," Proc. IEEE, v. 63, 1975, pp. 550560. MR 0451632 (56:9914)
 [2]
 R. C. AGARWAL & C. S. BURRUS, "Fast convolution using Fermat number transforms with applications to digital filtering," IEEE Trans. Acoust. Speech Signal Processing, v. 22, 1974, pp. 8799. MR 0398650 (53:2501)
 [3]
 R. C. AGARWAL & C. S. BURRUS, "Fast onedimensional convolution by multidimensional techniques," IEEE Trans. Acoust. Speech Signal Processing, v. 22, 1974, pp. 110. MR 0401340 (53:5169)
 [4]
 R. C. AGARWAL & J. W. COOLEY, "New algorithms for digital convolution," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 392409.
 [5]
 R. C. GONZALEZ & P. WINTZ, Digital Image Processing, AddisonWesley, Reading, Mass., 1977. MR 0459042 (56:17240)
 [6]
 J. JUSTESEN, "On the complexity of decoding ReedSolomon codes," IEEE Trans. Inform. Theory, v. 22, 1976, pp. 237238. MR 0465505 (57:5404)
 [7]
 D. KIBLER, "Necessary and sufficient conditions for the existence of the modular Fourier transform: Comments on 'Number theoretic transforms to implement fast digital convolution'," Proc. IEEE, v. 65, 1977, pp. 265267. MR 0490402 (58:9748)
 [8]
 S. LANG, Algebra, AddisonWesley, Reading, Mass., 1965. MR 0197234 (33:5416)
 [9]
 D. P. MAHER, TwoDimensional Convolution Using Ring Extensions, Proc. Second Annual Workshop on Information Linkage Between Mathematics and Industry, Academic Press, New York, 1980. MR 592274 (82a:94021)
 [10]
 F. J. MacWILLIAMS &. N. J. A. SLOANE, The Theory of ErrorCorrecting Codes, NorthHolland, Amsterdam, 1977.
 [11]
 H. MURAKAMI, I. S. REED & L. R. WELCH, "A transform decoder for ReedSolomon codes in multipleuser communication systems," IEEE Trans. Inform. Theory, v. 23, 1977, pp. 675683. MR 0469496 (57:9282)
 [12]
 P. J. NICHOLSON, "Algebraic theory of finite Fourier transforms," J. Comput. System Sci., v. 5, 1971, pp. 524527. MR 0286905 (44:4112)
 [13]
 H. J. NUSSBAUMER, "Digital filtering using pseudo Fermat number transforms," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 7983.
 [14]
 H. J. NUSSBAUMER & P. QUANDALLE, "Computation of convolutions and discrete Fourier transforms by polynomial transforms," IBM J. Res. Develop., v. 22, 1978, pp. 134144. MR 0471260 (57:10997)
 [15]
 J. M. POLLARD, "The fast Fourier transform in a finite field," Math. Comp., v. 25, 1971, pp. 365374. MR 0301966 (46:1120)
 [16]
 C. M. RADER, "Discrete convolutions via Mersenne transforms," IEEE Trans. Comput., v. 21, 1972, pp. 12691273. MR 0438672 (55:11580)
 [17]
 I. S. REED & T. K. TRUONG, "Complex integer convolutions over a direct sum of Galois fields," IEEE Trans. Inform. Theory, v. 21, 1975, pp. 657661. MR 0435049 (55:8011)
 [18]
 M. C. VANWORMHOUDT, "On number theoretic transforms in residue class rings," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 585586.
 [19]
 E. VEGH & L. M. LIEBOWITZ, Fast Complex Convolution Using Number Theoretic Transforms, NRL Report 7935, Naval Research Lab., Washington, D.C., 1975, pp. 113.
 [20]
 S. WINOGRAD, Some Bilinear Forms Whose Multiplicative Complexity Depends on the Field of Constants, IBM Research Report RC 5669, Thomas J. Watson Research Center, Yorktown Heights, N. Y., 1975. MR 0468322 (57:8158)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
1004,
94B35
Retrieve articles in all journals
with MSC:
1004,
94B35
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198005728533
PII:
S 00255718(1980)05728533
Article copyright:
© Copyright 1980
American Mathematical Society
