High-end embedded wireless communication applications demand high performance, strict low power, and in-field reprogrammability to follow the evolving standards. Today's single-core GPPs or DSPs cannot satisfy the challenging market performance requirements. Through specially tailoring individual processor core architectures to best fit a set of dedicated applications, heterogeneous multi-core architectures can maximize performance while mitigating area costs and power consumption. In this paper, we introduce new heterogeneous multi-core architectures using coarse-grained dynamically reconfigurable processors. The multi-core system has been tailored for the performance intensive WIMAX physical layer. Both WiMAX transmitter and receiver are partitioned and mapped on to the proposed heterogeneous architectures. An exploration algorithm is proposed to search the design space for multi-core systems to find suitable solutions under specific system and performance constraints. Results demonstrate that our heterogeneous multi-core architectures can provide throughputs of up to 8.7 Mbps and 2.4 Mbps for transmitter and receiver, respectively, meanwhile achieving a ratio of throughput to area at −200 Kbps per mm² for the overall WiMAX physical layer.