The discrimination of ECG signals is of crucial importance in clinical diagnoses of cardiac diseases. Manual analysis of ECG signals is very complex and time consuming task due to their composite nature. This paper proposes a novel scheme for reliable automatic classification of ECG signals into normal and three different abnormal (arrhythmia affected) categories. The feature extraction is based on an amalgamation of discrete cosine transform and random projection for dimensionality reduction. Furthermore, the classification is performed using random forest algorithm. The performance of the proposed scheme is evaluated on the restricted subset of ECG recordings from MIT-BIH arrhythmia database. In the experiments, a near perfect recognition accuracies of 99.33% and 99%, depending on the definition of projection matrix, are achieved with only 50 random projected coefficients; i.e. after considerable dimensionality reduction of the input ECG signal.