The paper introduces a new concept of Hierarchical Cellular Automata (HCA) employed in the design of on-chip hierarchical test pattern generator (TPG). The theory of HCA is developed over the Galois Extension Field GF(2^{p^q^r{..}}), where each cell can store a symbol in the extension field GF(2^{p^q^r{..}}). In designing the TPG based on the hierarchical structure of GF(2^{p^q^r{..}}) CA, we exploit the hierarchical structure of the Circuit Under Test (CUT). A methodology to tune the extension field parameters p, q, r,..., has been proposed in the design of CATPG (CA based Test Pattern Generator). Availability of hierarchical description of the CUT leads to a better tuning of CATPG, which results in maximal fault coverage in a given CUT. The experimental results clearly establish the fact that - higher fault coverage is achieved with the Hierarchical CA based TPG than that could be achieved with other structures, such as LFSR, Phase-Shift LFSR, GLFSR or GF(2) CA based TPGs.