Computationally intensive sinusoidal transforms such as the Fast Fourier Transform (FFT) and Discrete Cosine Transform (DCT) play a large role in science and engineering. The DCT has found valuable application in image and video processing. Its broad use has prompted many researchers to seek to improve its computational properties.
In the DCT, multiplication by irrational constants has been identified as a source of error, due to the introduction of quantization error. Efforts to overcome this quantization error have led to the relatively recent application of Algebraic Integer (AI) representations, by Dimitrov. The use of AI allows the irrational constants to be encoded, without quantization error. Numbers encoded in AI can be easily operated on by the arithmetic operations of addition, subtraction, and multiplication, all without the introduction of quantization error. A large computational penalty is paid when the AI encoded number, is reconstructed into a single number, using a process known as the Final Reconstruction Step (FRS).
This research investigates and develops a large number of novel designs for the FRS, in the application of 2D AI to the 2D DCT. These designs include the application of Multiple Constant Multiplication (MCM) and a substitution method, to reduce the computational complexity of the FRS. These new designs offer a significant improvement in Mean-Squared Error (MSE) and computational complexity, in comparison with standard FRS designs.
This research also provides a comprehensive comparative analysis of AI methods versus non-AI methods for the 2D DCT, and finds that non-AI methods are superior to AI in many cases, for the metrics of MSE and computational complexity, despite the significant FRS improvements reported in this thesis. For the case of area-limited designs, this thesis demonstrates the superiority of the AI method over the non-AI method, by the use of a single, multiplexed FRS stage.