A control channel generation method, a control channel decoding method, and a BS and an MS for implementing the methods are provided. The control channel generation method includes placing a frame control header (FCH) and a MAP within a TTI and generating a control channel for an enhanced communication system at a position after the MAP within the TTI. Another control channel generation method includes generating a control channel for the enhanced communication system and placing an FCH and a preamble at a position after the control channel. These methods enable implementation of an enhanced system that overcomes problems of the legacy system while minimizing influence exerted upon legacy MSs in the case where the base station generates a new control channel for a new MS or where an MS decodes a new control channel.