It is known that one of the essential building blocks of turbo codes is the interleaver and its design using random, semi-random (S-Random) and deterministic permutations. In this paper, two new types of turbo code interleavers, Modified Block S-Random (MBSR) interleaver and Modified Matched S-Random (MMSR) interleaver are proposed. The design algorithm for the new interleavers is described in depth, and the simulation results are compared to the two new interleavers with different existing  interleavers based on the BER (Bit Error Rate) performances of the turbo codes. Through the simulation, we find a better performance of the MBSR interleaver than random and practical interleavers. In addition, the performance of MMSR interleaver is close to the code matched interleaver at different frame sizes and with less complex design.