Traditional compressed sensing considers sampling a 1D signal. For a multidimensional signal, if reshaped into a vector, the required size of the sensing matrix becomes dramatically large, which increases the storage and computational complexity significantly. To solve this problem, we propose to reshape the multidimensional signal into a 2D signal and sample the 2D signal using compressed sensing column by column with the same sensing matrix. It is referred to as parallel compressed sensing, and it has much lower storage and computational complexity. For a given reconstruction performance of parallel compressed sensing, if a so-called acceptable permutation is applied to the 2D signal, we show that the corresponding sensing matrix has a smaller required order of restricted isometry property condition, and thus, storage and computation requirements are further lowered. A zigzag-scan-based permutation, which is shown to be particularly useful for signals satisfying a layer model, is introduced and investigated. As an application of the parallel compressed sensing with the zigzag-scan-based permutation, a video compression scheme is presented. It is shown that the zigzag-scan-based permutation increases the peak signal-to-noise ratio of reconstructed images and video frames.