Phase change memory (PCM) is a promising next generation nonvolatile memory. Despite the currently popular charge-based storage techniques, PCM leverages a much more scalable thermal-resistive mechanism that enables sub-10 nm feature sizes. To realize PCM's potential, there are a number of technical challenges that need to be addressed, including limited wear endurance and high energy consumption of bit writes. Our work introduces a novel set of tools and methodologies for encoding data on PCM that optimizes its write performance. We develop a framework which exploits asymmetries in PCM read/write. We show that this coding problem is NP-complete. To provide a tractable solution, we propose two different methods: the first uses integer linear programming, and the second leverages dynamic programming to find an approximation of the optimal solution. Our methods target both single and multi-level cell PCM and can be directly applied to any asymmetric nonvolatile memory with bit-level accessibility. We further optimize our codes by leveraging data distributions. We devise a low-overhead architecture for the encoder module which can be easily integrated within the existing computer memory architecture. We demonstrate the applicability, low overhead, and efficiency of our proposed framework with extensive evaluations.