MASK DATA CORRECTION APPARATUS, FOURIER TRANSFORMATION APPARATUS, UP SAMPLING APPARATUS, DOWN SAMPLING APPARATUS, METHOD OF MANUFACTURING TRANSFER MASK, AND METHOD OF MANUFACTURING DEVICE HAVING PATTERN STRUCTURE

A mask data correction apparatus that can increase efficiency of processing while maintaining high accuracy by effectively using the hierarchical structure of a layout data: A Fourier transformation part performs Fourier transformation of base elements defined by the layout data to obtain Fourier images of the base elements. A synthesizing part superimposes, based on the hierarchical structure, the Fourier images of the base elements in Fourier space, to obtain a Fourier image of the entire graphic. A spatial filter part subjects the Fourier image of the entire graphic to spatial filter processing that corresponds to distortion expected in a manufacturing process. An inverse Fourier transformation part performs inverse Fourier transformation of the Fourier image after spatial filter processing, to obtain the inverse Fourier image reflecting the distortion. The graphic defined by the layout data is compared with the graphic of which inverse Fourier image has been transformed, and is corrected in such a direction as to suppress distortion, and then is outputted as a mask data.