Abstract: Whenever inspected by humans, reconstructed signals should not be distinguished from real ones. Typically, such a high perceptual quality comes at the price of high reconstruction error.We study this distortion-perception (DP) tradeoff over finite-alphabet channels, for the Wasserstein-$1$ distance as the perception index, and an arbitrary distortion matrix. We show that computing the DP function and the optimalreconstructions is equivalent to solving a set of linear programming problems. We prove that the DP curve is a piecewise linear function of the perception index, and derive a closed-form expression for the case of binary sources.