In this work, we present a distortion-based erasure code for realizing unequal error protection in video delivery services. Prior to transmission, the resulting distortion caused by packet erasure is estimated for each of the video packets. This Information Is used to protect the video packets with higher distortion values strongly, whereas video packets with very low distortion values are not worth being protected. We present a local search algorithm that delivers near-optimal parity codes which minimize the expected overall distortion at the receiver. Furthermore, we suggest the deployment of our FEC erasure code at video proxies located at the edge to access networks with high packet erasure rates (e.g. mobile networks). This helps detecting and correcting packet losses efficiently, by tailoring the error protection code characteristics to the observed packet erasure rate of the receiver. Our erasure code is a parity code and relics solely on XOR-operations for encoding and decoding; hence, it shows very high efficiency compared to other more sophisticated codes. Simulation results show that our introduced erasure code outperforms the classical Reed-Solomon erasure codes in terms of perceived video quality, while running considerably faster.