The design of a satellite mobile multimedia communication system operating at Ka band and using synchronous CDMA is presented. The air interface described in the paper was derived taking into account the requirements induced by the provision of multimedia services to compact portable and mobile terminals. In order to minimize the complexity of the satellite payload, the concept of partial frequency reuse is introduced. A novel algorithm based on evolutionary theory is derived in order to optimize the corresponding link dimensioning. The satellite payload is described, and techniques reducing the computational requirements are proposed. It is then shown that the on-board complexity associated with the given design is within acceptable technological limits.