This paper is on the waveform design of joint radar and communication systems. Focusing on permutation code based random stepped frequency waveforms, we present a new joint radar and communication system that has improved communication error rate performance when compared to existing approaches. More specifically, we propose a subset selection process to improve the Hamming distance between communication waveforms. An efficient encoding scheme is proposed to map the information symbols to selected permutations. Further, an optimal communication receiver based on integer programming followed by a more efficient sub-optimal receiver based on the Hungarian algorithm is also proposed. Considering the optimum maximum likelihood detection, the block error probability is analyzed under both additive white Gaussian noise channels and Rician fading channels. Finally, we discuss the radar performance under the new system and highlight that it has negligible effect on the radar local and global accuracy.