RULES FOR MULTIDIMENSIONAL MULTIRATE STRUCTURES

This paper identifies a comprehensive set of compact rules and efficie nt algorithms for simplifying and rearranging structures common in mul tidimentional multirate signal processing. We extend the 1-D rules rep orted by Crochiere and Rabiner, especially the many equivalent forms o f cascades of upsamplers and downsamplers. We also include rules repor ted by other authors for completeness. The extension to m-D is based p rimarily on the Smith form decomposition of resampling (nonsingular in teger square) matrices. The Smith form converts non-separable multidim ensional operations into separable ones by means a shuffling of input samples and a reshuffling of the separable operations. Based on the Sm ith form, we have developed algorithms for 1) computing coset vectors 2) finding greatest common sublattices 3) simplifying cascades of up/d ownsampling operations. The algorithms and rules are put together in a form that can be implemented efficiently in a symbolic algebra packag e. We have encoded the knowledge in the commercially available Mathema tica environment.